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

arranging-coins(easy)

Math.

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

combination-sum-iv(medium)

Knapsack problem. Just note the order of the loops and which loop is the outer one.
As for the follow-up, I think we should add the limitation that we can only use a negative number at most once, or there could be infinite combinations. And then to solve this new problem, my idea is run 01-knapsack problem to initialize the array dp. This is just what I think about, and I cannot guarantee it is correct.

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

generate-random-point-in-a-circle(medium)

A simplest way is to use rejection sampling, which I have mentioned before.
However, my intuition is to pick a radius and a radian randomly, which seems like quite easy. However, there exists a pitfall that the probability of a point with a larger radius should be larger than that with a smaller radius.

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

maximum-depth-of-n-ary-tree(easy)

Recursion.

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

minimum-ascii-delete-sum-for-two-strings(medium)

DP. The same as longest common subsequence.

  • Time complexity: O(s1.length*s2.length).
  • Space complexity: O(s1.length*s2.length).

n-queens-ii(medium)

The same as n-queens which can be solved using backtracking.

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

optimal-account-balancing(hard)

It can be converted to that some people need to pay and some people need to get paid, and the question is what is the least transactions.
At first, it looks like a network flow(min cost max flow) problem. However, whatever how much you pay, it just count as 1 transaction, which does not meet the requirement of network flow.
So, we should search for the result. Then, I wrote a quite complicated DFS and it got to be too slow.
Finally, I found a really brilliant DFS method:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void dfs(int x, int cs) {
    if (x >= out.size()) {
        res = min(res, cs);
        return;
    }
    if (out[x] == 0) dfs(x + 1, cs);
    else {
        for (int i = x + 1; i < out.size(); i ++) {
            if (out[i] * out[x] >= 0) continue;
            out[i] += out[x]; // brilliant! use i to replace x to pay or get paied
            dfs(x + 1, cs + 1);
            out[i] -= out[x];
        }
    }
}
  • Time complexity: O(n!).
  • Space complexity: O(n).

permutation-sequence(easy)

It is easy to calculate there are how many permutations start with a certain number.

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

russian-doll-envelopes(medium)

The same as longest increasing subsequence after sorting the array by the width.
One simple approach is that dp[i] denotes the length of the longest increasing subsequence end with the i-th element, which is O(n^2).
Another faster approach is that dp[i] denotes the smallest ending element for the subsequence with the length of i, which is O(nlogn).

A trick is [3, 4] cannot contains [3, 3], so we need to put [3, 4] before [3, 3] when sorting otherwise it will be counted as an increasing number if the order is [3, 3], [3, 4].

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

shortest-path-to-get-all-keys(hard)

State compressed dijkstra(optimized by PQ)
dis[i][state] means the person is at position i and state consists of what keys he has.

  • Time complexity: O(n2^klog(n*2^k)).
  • Space complexity: O(n*2^k).

word-pattern-ii(medium)

Backtracking. The most difficult parts are how to solve it concisely(I think my implementation is elegant, ^_^) and hwo to optimize it.
What I use for optimization is an argument of remaining length for patterns out of the map.

  • Time complexity: It is quite hard to tell because of the optimization.
  • Space complexity: O(str,.length).