# Posts published in December 2017

Problem:

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:

and

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

Idea:

C ++ / Serialization

Time complexity: O(n^2)

Space complexity: O(n^2)

C++ / unique id with integer key

Time complexity: O(n)

Space complexity: O(n)

C++ / unique id with integer key single hashtable

Time complexity: O(n)

Space complexity: O(n)

Java

Time complexity: O(n)

Space complexity: O(n)

Python3

Related Problems:

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++

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.

# Solution 2: DFS w/o backtracking

## C++

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++

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)

Mission News Theme by Compete Themes.