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

subarray-sums-divisible-by-k(medium)

I have to admit that it’s a good problem and it seems pretty hard at first glance. However, if you know:

  1. a little about congruence group, the solution will be very straightforward;
  2. sum of a subarray can be represented using two the difference between two prefix sums.
  • Time complexity: O(n).
  • Space complexity: O(n).

interval-list-intersections(easy)

It’s a quite common interval merge problem. The solution is:

  1. sort if it’s out of order;
  2. use a pointer to indicate the next candidate which can contribute to the results.

THere are two lists, so we’ll use two pointers for them respectively.

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

basic-calculator-ii(medium)

Classic calculator problem: two stacks. One for operands(numbers), and one for operators. Use the priority(or weight) of the operators to decide whether it’s time to calculate.
This problem is simplified because there’s no brackets.

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

time-based-key-value-store(easy)

unordered_map<string, set<pair<int, string>>> key_nts_val;
Another trick is to use set.lower_bound(x) to search the largest number smaller than x.
Hint: use negatives.

  • Time complexity: O(logn) for each call.
  • Space complexity: O(n).

reorder-log-files(medium)

Customize the compare function.
Here’s a brief summary of how to customize the compare function.

1
2
3
4
static bool cmp(const string& a, const string& b) {
    // b is the former number, a is the later number
    // false means not to swap
}

Note we should use stable_sort because sort will keep the original order of the array.

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

odd-even-jump(medium)

You should notice that jump is always from left to right, which means there’s no aftereffects. Thus, the first idea we are supposed to come up with is DP.

jp[0][i]: the index you are at when you finish an even jump at i.
jp[1][i]: the index you are at when you finish an odd jump at i.

dp[0][i]: the number of good starting indexes if your next jump is an even jump at i.
dp[1][i]: the number of good starting indexes if your next jump is an odd jump at i.

State transfer:

1
2
if (~jp[0][i]) dp[0][jp[0][i]] += dp[1][i];
if (~jp[1][i]) dp[1][jp[1][i]] += dp[0][i];

A trick is how to use lower_bound to find the largest value less than x, which is the same as time-based-key-value-store(easy).

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