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

minimum-cost-for-tickets(medium)

The straightforward way is dp day by day.
dp[i]: the minimum cost for tickets before day i.
The state transfer is:

1
2
3
4
if (!mp[i]) dp[i] = dp[i - 1];
dp[i] = min(dp[i], dp[i - 1] + costs[0]);
if (i >= 7) dp[i] = min(dp[i], dp[i - 7] + costs[1]);
if (i >= 30) dp[i] = min(dp[i], dp[i - 30] + costs[2]);

However, here is a trick: the result could not be dp[365].
Another solution is much brighter and faster: dp[i] indicates the minimum cost for tickets from day[i] to the last day.
The state transfer is:

1
2
3
4
5
6
7
8
9
10
int n1 = n - 1, n7 = n - 1, n30 = n - 1;
for (int i = n - 1; i >= 0; i --) {
    while (days[n1] >= days[i] + 1) n1 --;
    while (days[n7] >= days[i] + 7) n7 --;
    while (days[n30] >= days[i] + 30) n30 --;

    dp[i] = min(dp[i], dp[n1 + 1] + costs[0]);
    dp[i] = min(dp[i], dp[n7 + 1] + costs[1]);
    dp[i] = min(dp[i], dp[n30 + 1] + costs[2]);
}
  • Time complexity: O(400), or O(n).
  • Space complexity: O(400), or O(n).

prison-cells-after-n-days(easy)

The first element and the last element will become 0 and will never change after the first round. So, the total of possible states is 2^6 + 1. Thus, we can brute force the cycle and its length.

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

squares-of-a-sorted-array(easy)

The largest square is either the smallest negative or the largest positive. So, we can use two pointers to scan the array from head and tail respectively.

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

verifying-an-alien-dictionary(easy)

String comparison.

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

fibonacci-number(medium)

Please assume n can be extremely large and the values will never overflow or the values will module a specific number.
Then the solution will be matrix fast power.

1
2
3
{{0, 1, 0},       {{0},  F(0)     {{1},  F(1)
{0, 0, 1},     *   {1},  F(1)  =   {1},  F(2)
{0, 1, 1}}         {1}}  F(2)      {2}}  F(3)
  • Time complexity: O(logn).
  • Space complexity: O(1).

basic-calculator-iii(hard)

This problem can be quite annoying. Just note that:

  1. The curly brackets should have the lowest weights.
  2. This kind of expression: -1-(-1). To handle this, I use a flag to indicate that a operator can follow a bracket.
  • Time complexity: O(n).
  • Space complexity: O(n).