Leetcode刷题记录帖

May 18th 2018 --- 1 Problem

## 304. Range Sum Query 2D - Immutable (Medium)

Including excluding principle.

May 19th 2018 --- 1 Problem

## 309. Best Time to Buy and Sell Stock with Cooldown (Medium)

``` java
for (int i = 0; i < prices.length; i ++) {
    int tmpCool = Math.max(cool, sell);
    sell = buy + prices[i];
    buy = Math.max(cool - prices[i], buy);
    cool = tmpCool;
}
```

May 20th 2018 --- 1 Problem

## 307. Range Sum Query - Mutable (Medium)

Binary indexed tree.

May 21st 2018 --- 1 Problem

## 301. Remove Invalid Parentheses (Hard)

Dynamic programming.

A valid string could be made up by two ways:
1. (string)
2. or  stringa + stringb

Then use DP or DFS based on these two rules.

May 22nd 2018 --- 1 Problem

## 306. Additive Number (Medium)

These methods are all very useful here:

```java
last = Long.parseLong(sa);
next = Long.parseLong(sb);

String tmps = Long.valueOf(tmp).toString();

if (!num.substring(base, num.length()).startsWith(tmps))
    break;
```

### Faults:
1. **[RE]** Input maybe larger than integer.

May 23rd 2018 --- 1 Problem

## 310. Minimum Height Trees (Medium)

For every node, to calculate its depth, there are two depths to compare with: the bottom-up depth of its deepest son, or the top-down depth from its father. The top-down depth of its father may come from two ways: its own father, or another child.

Here is own solution:

1. One DFS, calculate all bottom-up depth, record the deepest child and second deepest child for each node.
2. Another DFS, calculate the top-down depth for each node and get the final depth. For each node, compare its top-down depth and bottom-up depth. And we need to pass its top-down depth to its children: the top-down depth of its own, or the depth of its son's brother. We recorded the two deepest children for each node, so the brother's depth will always be avaliable.

Finally, find the nodes with shallowest depth.

May 24th 2018 --- 1 Problem

## 312. Burst Balloons (Hard)

Dynamic programming.

f[a][b] means all the balloons between a and b are burst. The last balloon be burst would be any balloon c between a and b. So we have:

```java
f[a][b] = Math.max(f[a][c] + f[c][b] + nums[a] * nums[c] * nums[b]);
```
nums[-1] and nums[n] would be helpful, add them in!

May 25th 2018 --- 1 Problem

## 313. Super Ugly Number (Medium)

The same as #264 but we got k primes here other than 3 primes. So instead of compare them by hand, we will use a priority queue to maintain the minimum next answer. Be careful will the duplicates.

May 26th 2018 --- 2 Problems

## 315. Count of Smaller Numbers After Self (Hard)

Sort numbers by them value and build binary indexed tree on there original index.

## 316. Remove Duplicate Letters (Hard)

Scan backwards. If every character already appeared at least once starts from position P, then any position before P is avaliable for an answer. So try to find the smallest character before P to get the best answer. After fix the position of this character, call the solve function again to fix the other ones.

May 27th 2018 --- 4 Problems

## 840. Magic Squares In Grid (Easy)

Scan.

### Faults:
1. **[WA]** Input maybe larger than 9.
2. **[WA]** Input maybe smaller than 1.

## 841. Keys and Rooms (Medium)

BFS.

## 842. Split Array into Fibonacci Sequence (Medium)

Same as #306.

### Faults:
1. **[RE]** Input maybe larger than long.

## 843. Guess the Word (Hard)

Record all the tries and randomize.