Leetcode刷题记录帖

May 8th 2018 --- 1 Problem

## 274. H-Index (Medium)

Sort the array. Scan the array to find some entry that its value equals to the number of entries larger or equal to it.

Be careful of the numbers with same value.

May 9th 2018 --- 1 Problem

## 273. Integer to English Words (Hard)

Interpret it bit by bit ...
Pay attention to special occasions like 11-19 or zero.

One very useful method here:
``` java
    String.join("-", ans);
```

May 10th 2018 --- 1 Problem

## 274. H-Index (Medium)

Sort the array. Scan the array to find some entry that its value equals to the number of entries larger or equal to it.

May 11th 2018 --- 1 Problem

## 279. Perfect Squares (Medium)

Dynamic programming.

``` java
ans[k] = Math.min(ans[k], ans[k - j * j] + 1)
```

May 13th 2018 --- 1 Problem

## 284. Peeking Iterator (Medium)

When you do peek(), just do next(), but use a variable to store the value. Keep returning this value to peek() until next next() request appears.

### Faults:
1.**[CE]** Confused 'left' and 'flag'.

补充内容 (2018-5-13 00:26):
May 12th 2018

May 13th 2018 --- 4 Problems

## 832. Flipping an Image (Easy)

Swap an array.

## 833. Find And Replace in String (Medium)

The only problem is if you replace some substring and its length is not the same, it will effect other replacements after.

So we could do the replacments backwards, just sort the index in ascending order in advance.

## 834. Sum of Distances in Tree (Hard)

Firstly, calculate `size[r]` (the size of subtree which has r as the root) and `collect[r]` (sum the distance from each node to root r) through recursion from bottom to top. Notice that `collect[r] += collect[son] + size[son]`.

Then, we could calculate the answer `dist[]` by `size[]` and `collect[root]` (`collect[root] == dist[root]`). Here is one important conclusion (`son` is one child of `r`'s ):

``` java
dist[son] = dist[root] - size[son] + (N - size[son]);
dist[son] = dist[root] + N - 2 * size[son]; // they are the same
```

## 835. Image Overlap (Medium)

Damn question.

### Faults:
1. **[WA]** Mind the difference between sliding, translation and rotation.

May 14th 2018 --- 1 Problem

## 287. Find the Duplicate Number (Medium)

Consider each number an linkedlist from the value of its index to the number. Then there will be several linkedlists point to the same node. In other words, we need to find a cycle in a linked list.

Then it is the same as #142.

May 15th 2018 --- 1 Problem

## 299. Bulls and Cows (Medium)

Use one array to count characters.

May 16th 2018 --- 1 Problem

## 282. Expression Add Operators (Hard)

### 1. Recursion with the record of last successive multiplys

Easier and clearer way.

### 2. Generate the whole and calculate by convert infix to postfix

One recursion to cut the nums, another recursion to generate operators.

Then use convert infix expression to postfix to calculate the value.

Compared with above solution, this one is quite complicated. I spent a lot of time on nearly 100 lines of code.

May 17th 2018 --- 4 Problems

## 289. Game of Life (Medium)

The problem is we could not display the two status with one bit at the same time.

Then we could use two bits! Last bit for status at this turn, and first bit for status at next turn!

## 295. Find Median from Data Stream (Hard)

### 1. Two Priority Queue

Two priority queue, one for the left half and one for the right.
Maintain the capacity of each priority queue according to sum size.

### 2. Binary Search Tree

Always search for the middle one or two in the BST.

## 297. Serialize and Deserialize Binary Tree (Hard)

Convert the tree to preorder traversal, put "null" for null TreeNodes.

## 300. Longest Increasing Subsequence (Medium)

The classical optimization (nlog(n) by binary search) for longest increasing subsequence.