My code can be viewed in my github: Proverbs Github.
The following difficulty is defined by myself.
1-bit-and-2-bit-characters(easy)
Check from left to right.
- Time complexity: O(n).
- Space complexity: O(1).
construct-binary-tree-from-inorder-and-postorder-traversal(easy)
The same as construct BST from inorder and preorder traversal.
- Time complexity: O(n^2) in the worst case.
- Space complexity: O(n).
construct-quad-tree(easy)
Just be careful to coordinates.
- Time complexity: O(n^2).
- Space complexity: O(n^2).
find-and-replace-pattern(easy)
Pattern matching need two mappings. One from pattern to string, another from string to pattern.
- Time complexity: O(n * length).
- Space complexity: O(#char).
length-of-longest-fibonacci-subsequence(medium)
DP. dp[i][j]: longest subsequence given the last two elements which is A[j] and A[i].
The state transition is O(1) because the state can only be updated by dp[j][idx(A[i] - A[j])].
Besides, pay attention to initialization.
- Time complexity: O(n^2).
- Space complexity: O(n^2).
longest-palindrome(easy)
Count characters appearing even times or odd times.
- Time complexity: O(n).
- Space complexity: O(#char).
range-sum-query-mutable(medium)
BIT(Binary Indexed Tree)(It’s my first time knowing its english name…).
A followup is modifying a sub-array each time.
Here is a summary of BIT.
By the way, the straightforward approach is, of course, segment tree.
- Time complexity: O(logn) for each update and query.
- Space complexity: O(n).
search-in-a-binary-search-tree(easy)
- Time complexity: O(logn), expected.
- Space complexity: O(1).
solve-the-equation(medium)
Count the scale of x and the constant for left part and right part, respectively.
The only thing you should note is the scale of x could be 0.
- Time complexity: O(n).
- Space complexity: O(1).