Press "Enter" to skip to content

Posts published in December 2017

花花酱 LeetCode 652. Find Duplicate Subtrees

652. Find Duplicate SubtreesMedium730151FavoriteShare

Given a binary tree, return all duplicate subtrees. For each kind of duplicate subtrees, you only need to return the root node of any one of them.

Two trees are duplicate if they have the same structure with same node values.

Example 1:

The following are two duplicate subtrees:

        1
       / \
      2   3
     /   / \
    4   2   4
       /
      4

2
/
4

and

4

Therefore, you need to return above trees’ root in the form of a list.

Solution 1: Serialization

Time complexity: O(n^2)
Space complexity: O(n^2)

C++

Solution 2: int id for each unique subtree

Time complexity: O(n)
Space complexity: O(n)

C++

花花酱 LeetCode 416. Partition Equal Subset Sum

题目大意:

给你一个正整数的数组,问你能否把元素划分成元素和相等的两组。

Problem:

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:

  1. Each of the array element will not exceed 100.
  2. The array size will not exceed 200.

Example 1:

Example 2:

 

Idea:

DP 动态规划

Solution:

Time complexity: O(n*sum)

Space complexity: O(sum)

C++

 

花花酱 LeetCode 753. Cracking the Safe

题目大意:让你构建一个最短字符串包含所有可能的密码。

There is a box protected by a password. The password is n digits, where each letter can be one of the first kdigits 0, 1, ..., k-1.

You can keep inputting the password, the password will automatically be matched against the last n digits entered.

For example, assuming the password is "345", I can open it when I type "012345", but I enter a total of 6 digits.

Please return any string of minimum length that is guaranteed to open the box after the entire string is inputted.

Example 1:

Example 2:

Note:

  1. n will be in the range [1, 4].
  2. k will be in the range [1, 10].
  3. k^n will be at most 4096.


Idea: Search

Solution 1: DFS w/ backtracking

C ++

Solution 2: DFS w/o backtracking

C++

花花酱 LeetCode 476. Number Complement

题目大意:给你一个正整数,输出和它互补的数(翻转所有的bits)。

Problem:

Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation.

Note:

  1. The given integer is guaranteed to fit within the range of a 32-bit signed integer.
  2. You could assume no leading zero bit in the integer’s binary representation.

Example 1:

Example 2:

Idea:

Bit



Solution:

C++

 

花花酱 LeetCode 367. Valid Perfect Square

题目大意:判断一个数是否是平方数。不能使用开根号函数。

Given a positive integer num, write a function which returns True if num is a perfect square else False.

Note: Do not use any built-in library function such as sqrt.

Example 1:

Example 2:

Idea:

Binary search

Solution:

C++

Time complexity: O(log(num))

Space complexity: O(1)