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

battleships-in-a-board(easy)

Because there is no two adjacent battleships, we can just count the top-left X in one pass.

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

best-meeting-point(medium)

Manhattan distance: x and y are independent.

Then we can just think about the problem of 1D, and the solution is quite direct: to find the median.

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

bulls-and-cows(easy)

Count using map. To avoid duplication, we can decrease the counter by one when there is a cow.

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

can-place-flowers(easy)

Greedy.

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

construct-binary-tree-from-preorder-and-postorder-traversal(medium)

The first element of preorder sequence which is the same as the last element of postorder sequence is the root.
Delete this element and then find first k elements of preorder sequence and postorder sequence which can make two same sets. Then there elements can be the left subtree which may not be unique.

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

contains-duplicate-iii(medium)

A straightforward method is to maintain a sliding window with the size of k. And then use a BST(set) to find the largest element smaller then current number and the least element larger then current number.
And Another quite brilliant method is bucketing. Details can be seen at: Link, which is O(n).

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

excel-sheet-column-number(easy)

Number based on 26.

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

fraction-addition-and-subtraction(medium)

GCD(Greatest Common Divisor) and LCM(Least Common Multiple).

1
2
3
4
int get_gcd(int a, int b) {
    if (!b) return a;
    return get_gcd(b, a % b);
}
  • Time complexity: O(length*log(#factions)).
  • Space complexity: O(1).

k-diff-pairs-in-an-array(easy)

Use map to eliminate duplicates. Or use two pointers after sorting.

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

kill-process(medium)

DFS on trees.
Build tree:

1
2
3
4
5
6
head.resize(n, -1);
void dfs(int x, vector<int>& res) {
    res.push_back(x);
    for (int i = head[x]; ~i; i = nxt[i])
        dfs(to[i], res);
}
  • Time complexity: O(n).
  • Space complexity: O(n).

minimum-area-rectangle(medium)

Use map to classify points according to x-coordinates. Then sort each class according to y-coordinates.
Enumerate two classes for left and right sides. Then, enumerate the top and bottom sides using map.

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

peak-index-in-a-mountain-array(easy)

Binary search.

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

permutations-ii(medium)

Use dfs to generate all permutations. Do not use the same number for more than one times in each round.

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

poor-pigs(hard)

It is a good math problem and this method is widely used.
Note the description could be misleading.
REF.

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

recover-binary-search-tree(medium)

The key point is to find which two elements are swapped.
One dfs from largest number to smallest number to find the larger one, another dfs from smallest number to largest number to find the smaller one.

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

remove-duplicates-from-sorted-list(easy)

Linked list operations.

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

special-binary-string(hard)

Every time we can only swap two special strings, so the result should always be a special string.
Represent a 01 string as “mountains, which is quite typical.”: Link.
Note that we should enumerate height from high to low. An example is 111000-1101110000.

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

split-array-largest-sum(medium)

Binary search the result.

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

sum-of-distances-in-tree(hard)

For the distance of a node, there are two parts: distance from its children and distance from its parent.
Suppose s[x] is the sum of distance from its children, p[x] is the sum of distance from its parent and n[x] is the number of nodes in its subtree.
Then s[x] and n[x] can be compute using DFS easily.
And p[x] = s[fa[x]] - (s[x] + n[x]) + p[x] + n[fa[x]] - n[x] + p[x] + p[fa[x]] + (N - n[fa[x]]) which can be compute using anther DFS.,

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

the-maze(medium)

DFS.

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

valid-parenthesis-string(medium)

DFS with cache to implement DP.
Cannot understand the greedy solution.

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

valid-square(easy)

Note that the sides do not need to be parallel to x or y axes. Use vectors’ dot product to check if two vectors are perpendicular to each other.

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