My code can be viewed in my github: Proverbs Github.
The following difficulty is defined by myself.
boundary-of-binary-tree(easy)
The top is the root, the left or right boundary is the “leftmost” or “rightmost” nodes. The remaining leaves are the bottom.
Use dfs to get the left boundary and leaves in the left subtree. And do the same thing for right boundary and leaves in the right subtree.
- Time complexity: O(n).
- Space complexity: O(n).
custom-sort-string(medium)
The easiest approach is to use quick sort and overwrite the compare function, which is O(nlogn).
However, there will only be at most 26 characters. Thus, we can use counting sort which is not based on comparison.
- Time complexity: O(s.length+t.length).
- Space complexity: extra O(26).
design-circular-queue(easy)
Circular queue’s size should be (1 + size of ordinary queue) in order to represent states of empty and full.
- Time complexity: O(1) for each operation.
- Space complexity: O(size).
encode-string-with-shortest-length(hard)
DP. dp[i][j]: shortest encoded string from s[i] to s[j], dp[i][j] can be modified by dp[i][k] + dp[k + 1][j] and a substring of s[i~j] which can form s[i~j] by repeating.
To check if there is a substring of s[i~j] which can form s[i~j] by repeating, we can use R-K Hash.
Greedy algorithm to encode from the longest duplicate substrings is wrong. e.g. aaabbbaaabbbaaabbbaaa
- Time complexity: O(n^3).
- Space complexity: O(n^2).
flipping-an-image(easy)
- Time complexity: O(row*col).
- Space complexity: O(row*col).
guess-number-higher-or-lower-ii(hard)
DP. dp[i][j] means the lowest cost to guess from i to j. dp[i][j] = min(i + max(dp[i][k - 1] + dp[k + 1][j])), which is O(n^3).
There is a quite challengeable solution which is O(n^2).
- Time complexity: O(n^3).
- Space complexity: O(^2).
implement-rand10-using-rand7(medium)
It is a typical method: Rejection Sampling.
- Time complexity: O(1) expected.
- Space complexity: O(n).
implement-stack-using-queues(medium)
Keep the order of queue except that the last element becomes the first when pushing.
- Time complexity: O(n) for push, O(1) for other functions.
- Space complexity: O(n).
insert-into-a-cyclic-sorted-list(medium)
Find the smallest and greatest nodes.
- Time complexity: O(n).
- Space complexity: O(1).
is-subsequence(easy)
Greedy algorithm.
- Time complexity: O(t.length).
- Space complexity: O(1).
knight-dialer(medium)
It is a simplest problem of fast power of matrix.
And the ordinary method is DP.
- Time complexity: O(logn).
- Space complexity: O(10).
maximize-distance-to-closest-person(easy)
Scan from left to right and keep track of a last pointer.
- Time complexity: O(n).
- Space complexity: O(1).
minimum-moves-to-equal-array-elements(medium)
The last state before all elements are equal is (n-1) elements are equal.
The last state before (n-1) elements are equal is (n-2) elements are equal.
…
That is the approach.
- Time complexity: O(nlogn).
- Space complexity: O(n).
odd-even-linked-list(easy)
Divide linked list to odd and even parts.
- Time complexity: O(n).
- Space complexity: O(1).
palindrome-permutation(easy)
There are no more than 2 characters which appear odd times.
- Time complexity: O(n).
- Space complexity: O(n).
rectangle-area(easy)
Sum of two areas subtract the overlapped area.
- Time complexity: O(1).
- Space complexity: O(1).
score-of-parentheses(easy)
Recursion.
- Time complexity: O(n).
- Space complexity: O(n).
search-in-rotated-sorted-array-ii(hard)
Maybe when I had a messy mind when I tried to solve it.
- Time complexity: O(n) in the worst case.
- Space complexity: O(1).
trapping-rain-water-ii(hard)
It a good problem. However, 1D solution is not applicable for 2D problem because there are many path for water to go down.
The solution is to use priority queue to maintain the minimum border and current height which means the shortest piece of the bucket for the new added point.
- Time complexity: O(nmlog(n*m)).
- Space complexity: O(n*m).