My code can be viewed in my github: Proverbs Github.
The following difficulty is defined by myself.

robot-return-to-origin(easy)

Use dx++/-- and dy++/-- to indicate the move of the robot.

  • Time complexity: O(n).
  • Space complexity: O(1).

reverse-vowels-of-a-string(easy)

Scan the string from left to right and save all vowels in order in an array. Then, replace the vowels from right to left according to the array. Another way is to use two pointers to walk the string from left and right respectively and swap the vowels.

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

maximum-xor-of-two-numbers-in-an-array(medium)

This problem is really classic and I love it. It’s a problem of “selecting the optimal pair” and a problem of " bitwise XOR". For the first problem, the basic idea is to enumerate each one, and compute the best with any other ones. Trie’s “find” function is exactly that.

  • Time complexity: O(32n).
  • Space complexity: O(n).

power-of-three(easy)

The easiest O(1) method is to calculate the maximum power of three within MAX_INT manually, and then all the other powers of three are all its factors.

  • Time complexity: O(1).
  • Space complexity: O(1).

k-closest-points-to-origin(medium)

The kind of problem is quite common(using Max Heap) now and it shouldn’t have been a “medium” problem. But the only reason why I marked it as “medium” is I can practice how to use STL Priority Queue with Comparator class.

  • Time complexity: O(nlogK).
  • Space complexity: O(K).

partition-labels(easy)

My straightforward idea is Greedy: to keep track of the occurrence of lowercase letters of both current string and the rest of the string. When there’s no letter occurring in both strings, I will make current string a new partition. It’s a solution with the time complexity of O(26n). However, there’s another solution which is much better in the Solution Page using next pointers.

  • Time complexity: O(26n), the better solution is O(n).
  • Space complexity: O(n).

min-cost-climbing-stairs(easy)

One of the easiest DP problems in Leetcode. Two ways of state transfer: one step of two steps.

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

gray-code(easy)

This is quite easy if you do know how to construct Gray Code: to unfold from 0 1 iteratively. For example:

1-bit Gray code:

1
2
0
1

2-bit Gray code:

1
2
3
4
5
(0) 0
(0) 1
------
(1) 1
(1) 0

3-bit Gray code:

1
2
3
4
5
6
7
8
9
(0) 0 0
(0) 0 1
(0) 1 1
(0) 1 0
-------
(1) 1 0
(1) 1 1
(1) 0 1
(1) 0 0
  • Time complexity: O(n).
  • Space complexity: O(2^n).

pascals-triangle-ii(easy)

Use circular array to save the space, if you are calculating row by row.

A smarter way is to calculate column by column.

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

valid-number(hard)

It’s not a real hard problem, it’s just nauseous: there are so many corner cases that you couldn’t cover they at the first shot or first several shots. My idea is to split in into 3 parts: integer, decimal, and exponential.

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

paint-house(easy)

The only the constraint is adjacent houses can’t be painted to the same color which is also a very common feature(no aftereffect) of DP.

State: dp[i][j]: lowest cost for painting first i houses and the ith house’s color is j.

State transfer: dp[i][j] = min(dp[i - 1][k] + cost[i][j]), where j != k.

  • Time complexity: O(3^2*n).
  • Space complexity: O(3n).

binary-tree-upside-down(easy)

Honestly, I didn’t understand the problem statement until I found another description in Discussion Page. We just need to rotate the original left child to the root, original root to the right child, original right child to left child. And do it recursively.

Note that only binary trees whose right child is either leaf node or NULL can do this.

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

second-minimum-node-in-a-binary-tree(easy)

There are only two kinds of cases:

  1. left child is the same as right child: return the smaller value of the “second-minimum-node” the left subtree and the right subtree.
  2. not the same: return the smaller value of the “second-minimum-node” the left subtree and the value of the root of the right subtree if the right child is larger, and vice versa.
  • Time complexity: O(n).
  • Space complexity: O(n).

can-i-win(hard)

For this problem, you need to know what is SG function. And then you will know for a given state, a person can either force a win or eventually reach a unavoidable lose.

If sg(state) is 1 if there exists a move which can reach a state1 whose sg value is -1.

If sg(state) is -1 if all states a move can reach have a value of 1.

  • Time complexity: O(2^#nums*tot).
  • Space complexity: O(2^#nums).

find-largest-value-in-each-tree-row(easy)

DFS with passing the depth at the same time, or BFS. In practical, BFS is faster but DFS uses less memory.

  • TIme complexity: O(n).
  • Space complexity: O(n).

sum-of-square-numbers(easy)

Same as two 2-sum using 2 pointers.

  • Time complexity: O(sqrt(n)).
  • Space complexity: O(sqrt(n)).