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

card-flipping-game(easy)

The description is kind of vague. Another description from discussion is:

Given an array of cards with numbers written on both sides and an infinite number of card flips, find the minimum number appearing on any card’s back which is not appearing on any card’s front.

And the solution is to find the smallest number which never appears on both sides of any card.

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

count-different-palindromic-subsequences(hard)

The most difficult point of this problem is how to deal with the duplicate subsequences.
dp[c][lt][rt]: number of different subsequences which start with c and end with c using letters in range [lt, rt].
The key point is when c == s[lt] == s[rt]:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
if (s[lt] == 'a' + c && s[rt] == 'a' + c) {
    if (lt + 1 == rt) {
        res = 2; // c, cc
        return res;
    }

    res = 1; // cc
    res += dfs(dp, s, c, lt + 1, rt - 1);
    if (dfs(dp, s, c, lt + 1, rt - 1)) res ++; // there exists at least one c, then 1 for cc...cc or c...c...c
    else res ++; // there exists no c, then 1 for c
    res %= mod;
    for (int i = 0; i < 4; i ++)
        if (i != c) {
            res += dfs(dp, s, i, lt + 1, rt - 1);
            res %= mod;
        }
}

PS: Why I got MLE if I used the resize function???

  • Time complexity: O(4*length^2).
  • Space complexity: O(4*length^2).

delete-node-in-a-linked-list(medium)

We do not know the root of the linked list, then we create a root by swapping current node with the next node.

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

design-snake-game(medium)

Use deque to represent the snake and use queue to represent the food.

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

h-index(hard)

The result must be from 1 to n.
So, we can sort the array and then enumerate the result and use binary search to check how many numbers are not less than the result.
This is the O(nlogn) method. However, there is a brilliant solution which applies the counting sort whose complexity is determined by range.
Again, the result must be from 1 to n, then all numbers larger than n are meaningless and we can change them to n to reduce the range.

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

longest-line-of-consecutive-one-in-matrix(medium)

Only check the top, left, top-left or top-right 1 for each line. Then, we can solve it in one pass.

  • Time complexity: O(row*col).
  • Space complexity: O(row*col).

longest-substring-with-at-least-k-repeating-characters(hard)

It is hard to apply sliding window, when we cannot determine how many unique letters should be in the sliding window.
So, we can enumerate the number of unique letters and then use 26 sliding windows for different numbers of unique letters.

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

network-delay-time(medium)

Shortest path from a single source point: SPFA.

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

next-greater-element-ii(easy)

Extend the array using itself and then use stack to get the first larger element on the right.

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

number-of-connected-components-in-an-undirected-graph(easy)

DFS.

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

partition-list(medium)

Take the elements not less than x out of the original list. Then connect two lists.

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

path-sum-ii(easy)

DFS.

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

random-pick-index(easy)

Use a map to store all indices of a number.

  • Time complexity: O(n) initialization, O(1) pick.
  • Space complexity: O(n).

same-tree(easy)

Do it recursively.

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

sentence-similarity(easy)

Use nested maps to store the similarities.

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

sum-of-subarray-minimums(medium)

I have misunderstood the problem sum-of-subsequence-widths to this problem. You can see the method at: Link.

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

the-maze-ii(medium)

Heap or priority_queue + Dijkstra.

  • Time complexity: O(colrowlog(row*col)).
  • Space complexity: O(col*row).