Leetcode刷题记录帖

Mar. 26th 2018 --- 9 Problems

## 105. Construct Binary Tree from Preorder and Inorder Traversal (Medium)

Recursion.

## 106. Construct Binary Tree from Inorder and Postorder Traversal (Medium)

Same with #105.

## 109. Convert Sorted List to Binary Search Tree (Medium)

Recursion. The recursion will cose O(log n) space and you will need O(n) space for the built tree. Other than these, the solution used O(1) extra space.

If you do the building in inorder, the order you create one node will be the same order as its order in the linked list.

## 113. Path Sum II (Medium)

Recursion.

Faults:

1. **[WA]** Node's value could be negative.

## 114. Flatten Binary Tree to Linked List (Medium)

Recursion. If root has left child L, then make his right child R L's rightest node's right child.

## 115. Distinct Subsequences (Hard)

DP. F[j] means the answer ends with s match first j characters of string t.

    f[j] = sum{f[k][j - 1] (k < i)}

## 116. Populating Next Right Pointers in Each Node (Medium)

Notice that only constant extra space could be used, which means neither data structures nor recursion are permitted.

We can take advantage of "next" to go through the tree. In order to know the first element in next level, we need an variable to record the first child of this level. When completing one node's next attribute, search in its father's brothers until you find a brother has at least one child.

## 117. Populating Next Right Pointers in Each Node II (Medium)

Same as #116.


## 120. Triangle (Medium)

DP. In order to use the same array all the time, you need to update the array from back in case the element you need will be covered.

Mar. 27th 2018 --- 4 Problems

## 123. Best Time to Buy and Sell Stock III (Hard)

1. O(N^2) DP.
2. O(N) + O(N) Scan.
3. O(N) + O(1) Scan. https://leetcode.com/problems/be ... est-Solution-with-O(n)-O(1).

## 124. Binary Tree Maximum Path Sum (Hard)

Recursion. Merge two path from its children or carry one path to its father.

Faults:

1. **[WA]** You can choose to obtain no value from children because the value maybe negative.

## 126. Word Ladder II (Hard)

BFS + DFS.

BFS search for shortest path and DFS print out all paths with such a length.

Build reverted edges during BFS, and search from end to start in the DFS.

(I think two-end BFS is too complicated here, and time performance improvement it brings is not very obvious.)

Faults:

1. **[TLE]** It will be too slow if do not clear the way (build new edges).
2. **[TLE]** Same as above.

## 127. Word Ladder (Medium)

Learned how to write two-end BFS.

Faults:

1. **[WA]** The endWord maybe not in the wordList.

请假。明天回奶奶家，要断网几天。

Apr. 1st 2018 --- 4 Problems

从奶奶家回来了！

## 152. Maximum Product Subarray (Medium)

Calculate the prefix product.

Pay attention to zeros.

Faults:

1. **[WA]** One single zero maybe the answer.

2. **[WA]** Same as above.


## 153. Find Minimum in Rotated Sorted Array (Medium)

Binary search.


# Weekly Contest 78

前两道题简单，比手速。当时状态不好，心态也差，没耐心连错好几次。
后面两道题一道概率题一道博弈论数学题，很陌生不会做。

后面两道题明天写。

## 809. Expressive Words (Medium)

Could construct one regex and then use String.matches(regex) to match them.

Faults:

1. **[WA]** Didn't process the last character of S.
1. **[WA]** Didn't process the last character of word.

## 811. Subdomain Visit Count (Easy)

Two ways to go through a HashMap:

    for (Map.Entry<String, Integer> entry : map.entrySet())
        result.add(entry.getValue() + " " + entry.getKey());

    Iterator iter = map.entrySet().iterator(); // map.ketSet().iterator()
    while (iter.hasNext()) {
        Map.Entry entry = (Map.Entry) iter.next();
        result.add(entry.getValue() + " " + entry.getKey());
    }

Faults:

1. **[WA]** Misplace key and value.

Apr. 2nd 2018 --- 8 Problems

## 128. Longest Consecutive Sequence (Hard)

Use a HashMap, for some number num, search for (num + 1).
1. If (num + 1) not exists, return 1;
2. If (num + 1) exists and has not been searched, search (num + 2);
3. if (num + 1) has been searched, return len(num + 1) + 1;

Faults:

1. **[WA]** Not enough corner case: the number could be the same.

## 129. Sum Root to Leaf Numbers (Medium)

Recursion.

## 130. Surrounded Regions (Medium)

BFS.

Always mind wether the array will be empty when you get a 2D array's length.

Faults:

1. **[RE]** Input 2D array maybe empty.

## 131. Palindrome Partitioning (Medium)

DP + BFS.

## 132. Palindrome Partitioning II (Hard)

DP + DP.

## 133. Clone Graph (Medium)

BFS.

Faults:

1. **[CE]** Queue.
2. **[RE]** Input maybe null.

## 808. Soup Servings (Medium)

DP.

The most conclusion in this problem is, when the N is so large (N / 25 > 500), the probability could be seen as 1

## 810. Chalkboard XOR Game (Hard)

https://leetcode.com/problems/chalkboard-xor-game/solution/

Apr. 9th 2018 --- 5 Problems

## 403. Frog Jump (Hard)

1. DFS: Actually, most of the fastest solutions are in DFS.
2. DP: i(the i-th stone), k(width of the last step is k), reach[k] is true when such a condition is reachable. You have i and k, you can use a map to check whether the stone at (stones - k) exists. Notice that the step increase at most 1 each time, so the largest jump width is (stones.length).
3. Better DP: Use a map of sets to record the steps to each stone, we don't need to enumerate the width anymoew. If one stone's set is empty, then it is unreachable, which replaces the reach[][].


Weekly Contest 79

# 812. Largest Triangle Area (Easy)

Both Heron Formula and determinant are okay.

Faults:

1. **[WA]** Something wrong with `Math.max(double, double)`? Use `Double.max(double, double)` next time.

# 813. Largest Sum of Averages (Medium)

O(N*N) DP.

1. Calculate prefix sum[];
2. Calculate avg[][] by sum[];
3. DP: res[k] k groups until the i-th number.

# 814. Binary Tree Pruning (Medium)

Recursion.

# 815. Bus Routes (Hard)

Convert the input array into map, then BFS.

**The most important optimization:** once you took some route, you will never take this route again in the best answer.

Faults:

1. **[TLE]** Not fast enough.
2. **[TLE]** Not fast enough.
3. **[TLE]** Not fast enough.

Apr. 9th 2018 --- 3 Problems

## 134. Gas Station (Medium)

### 1. Deque (My solution, O(N) + O(N))

Calculate price[] at first, according to `price= price[i - 1] + gas- cost`.

Maintain an ascending deque for the least price: before push in some value price at back, pop out any value larger than price; index i of price should also be recorded.

First scan: push all price[] into deque.

Second scan: If i is the head of the deque, pop it out. Push it to the back of the deque. Update all prices by one variable bias.

### 2. Scan (Best solution, O(N) + O(1))

Record `tank += gas - cost`, if `tank < 0` then `tank = 0, start = i + 1`.

One question is, could some station k between the oldStart and newStart become the start of the solution? Answer is no. If k is the solution instead of oldStart, which means the sum between oldStart and k is negative, then k will become our newStart, which draws contradiction.

Faults:

1. **[WA]** The ascending order should also be maintained when you push one element in the second time.

## 135. Candy (Hard)

Scan from left to right to make sure the number on the right is larger than left.

Scan again from right to left to make sure number on the left is larger than right.

## 137. Single Number II (Hard)

Learn how to solve all this kind of problems by this analysis:

https://leetcode.com/problems/si ... -sort-of-questions.

Apr. 10th 2018 --- 3 Problems

## 138. Copy List With Random Pointer (Medium)

### 1. HashMap (O(N), O(N))

The most obvious solution is to use a HashMap to store the map between original node and duplicated node.

### 2. Scan and Modify the Original Linked List (O(N), O(1))

This approach is much more interested. In order to save space, we modify the original linked list instead.

When copy a node, insert it into the linked list just after its origin. `dup = iter.next, iter.next = dup;` In such a way, the odd nodes in the list are original and the even nodes are duplicates.

Next, complete the random pointers of the duplicates.

At last, extract new list and restore the origin list.

### Faults:

1. **[TLE]** You need go to `iter.next.next` when you add a new node after `iter`.
2. **[RE]** Forget to make a copy before some node is changed.
3. **[RE]** Same as above.

## 139. Word Break (Medium)

(S is the length of string s, W is the longest length of words, and N is the number of words.)

### 1. KMP + DP (O((S+W)\*N, O(S\*N))

This is my solution.

First use KMP to match each word and string s to calculate array m[k], which means  whether the k-th word will match the substring end by position i in string s.

Then use DP to calculate f (wether the first i characters in string could be matched) by enumerate the words in the wordDict.

Array m[k] could be replaced by HashMap<String, HashSet>

### 2. HashSet + DP (O(S\*S), O(W\*N))

Instead of enumerate words during DP, this approach enumerate the length of substring to be matched. In such a way, you don't need to pretreat the strings by KMP, and you should put all the strings in a HashSet.

Which solution's performance is better depends on the distribute of the data.

### 3. DP (O(S\*S\*N), O(S))

This approach is even more violent. Don't use HashSet, just let the List provided by the system to do the searching.

## 140. Word Break II (Hard)

Memorized DFS.

### Faults:

1. **[WA]** Extra space in the output.
2. **[TLE]** Not enough optimization.
3. **[TLE]** Same as above.

可以的大兄弟

楼主加油！
最近也在刷题，准备今年秋天的全职:)