Leetcode刷题记录帖

专职刷题（争取）。
每天5-10题，具体根据难度和时间决定，争取3-4个月内刷完。
周日做Leetcode weekly contest。
语言Java，按照顺序刷（之前挑着做了一些），争取不跳题。

欢迎讨论或者互相监督！

补充内容 (2018-4-10 12:40):
我的Leetcode： https://leetcode.com/mintyc/
我的代码：https://github.com/mintycc/Onlin ... ree/master/Leetcode

wenluvLA 发表于 2018-5-28 06:40
感谢楼主分享刷题纪录！
这样督促自己刷题挺不错的
目前我也是每周末比Leetcode weekly contest

是的 Leetcode Weekly Contest坚持参加下来帮助会很大
一起加油！╭(′▽`)╭(′▽`)╯

Spet 17th 2018 --- 5 Problems

Weekly Contest 102

## 904. Fruit Into Baskets (Medium)

### Corner cases

1. Input maybe empty.
2. Input may have only one tree.
3. Input may have only one kind of trees.

### Bugs

1. [WA] After you clear one basket and put new fruit in, the new length should be the length of the subarray starting from last position of the eliminated fruit + 1 to the position now.

### Solution

#### Best Solution

The algorithm seems like LRU. Use pointers to record the two kind of fruits in your baskets and their recently visited position. When you facing a new tree, first check whether you already got this kind of fruit in you basket. If the answer is yes, increase your length and update recently visited position of this kind (basket). If the answer is no, clear the basket with the oldest recently visited position and put the new fruit in.

- Time complexity: O(n)
- Space complexity: O(1)

## 905. Sort Array By Parity (Easy)

### Corner Cases
1. Input array is empty.
2. All elements are odd or even.
3. Only one element in array.

### Bugs
1. Nope.

### Solution
#### Best Solution

One pointer i forwards and another pointer j backwards. Pointer i stops when it finds an odd number and pointer j stop when it find an even number. Swap elements at i and j. Continue.

- Time complexity: O(n)
- Space complexity: O(1)

## 906. Super Palindromes (Hard)

### Corner Cases
1. Use [L, L] on some specific number to test your program.
2. [1, 10^18 - 1] to test your time complexity.

### Bugs
1. [WA] `StringBuilder.reverse()` change the `StringBuilder` itself other than generate a new one.
2. [WA] The same as `StringBuilder.append()`.
3. Several trasfer functions between `String` and `Integer` does not support `StringBuilder` or `Long`.

### Solution
#### Best Solution

Enumerate a Integer, make a palindrome from it, get check wether the square of that palindrom is also a palindrome and falls into the right range. The range of square is [1, 10^18], so it would be enough for us to enumerate to 10^5.

Also, Long type would be enough to store those two inputs.

The question would be a nice practice to check if you are clear about the conversion between number, string and stringbuilder.

## 907. Sum of Subarray Minimus (Hard)

### Corner Cases
1. Input is empty.
2. Only one element in input.
3. All the elements in input are the same.

### Bugs
1. [WA] First time try to find out all `left[]` and `right[]` by one scan without any data structures.

### Solutions
#### Best Solution - Stack

Actually, the problem is trying to find the range for each number, for every subarries in this range, the number will be the subarray's minimum.

Then, the question is transferred into finding such `left[]` and `right[]` standing for the left and right side of each number's range, with the initial value the position of the number itself.

We utilize a stack here, scan the array forwards. Before you push a new element in, pop out all elements greated than it. The farthest `left[]` of the elements it poped out will be its `left[]`.

One special occasion is if there are duplicates in the array. The subarray including both of them should only be calculated once. The solution is: in one direction, we pop out all elements greater than new element in the stack; in the other direction, we pop out all elements greater than or equal to the new element.


## 786. Kth Smallest Prime Fraction (Hard)

This is a classic interview question from PonyAI.

### Corner Cases
1. Cases like [1, 3000] is strong enough.

### Bugs
1. Eps related operations are very delicated.
2. `Math.floor()` and `Math.ceil()` operations.

### Solutions
#### 1. Sort

N prime numbers in the array, then there will be at most n^2 fractions. Sort all of them and pick out the kth smallest one.

- Time complexity: o(n^2 log(n^2))
- Space complexity: o(n^2)

### HeapSort

Firstly add the smallest fraction into heap. Everytime you pop the top out of heap, push fractions next to it into the heap. Repeat this operation for K times.

- Time complexity: O(K log(n^2))
- Space complexity: O(n^2)

### Binary Search + TreeSet

Use binary search to enumerate the fractions from [0, 1], check if there is exactly K fractions from the array less than it (O(n) for each check). If so, find the greatest fractions less than it from the array. Such a operation could be done easily with the help of `TreeSet.floor()`.

- Time complexity: O(n log(1 / eps)) (1 / eps is nearly 10^7)
- Space complexity: O(n ^ 2)

May 5th 2018 --- 5 Problems

## 236. Lowest Common Ancestor of a Binary Tree (Medium)

### 1. Recursion O(N) + O(1)

Like #235, if p and q appear in two different children of root, then root is the answer. Otherwise search for answer in its children.

### 2. Fathers O(N) + O(N)

First find all nodes' fathers and store them in a map. Then keep going up from p and q until meet at some node (adjust them to the same depth at first).

### Faults:
1. **[WA]** Stop when p and q are the same, not the depth is zero.

## 238. Product of Array Except Self (Medium)

Scan twice.

## 239. Sliding Window Maximum (Hard)

### 1. Deque O(N) + O(N)

Maintain a descending deque with capacity k. Push new element into the end, pop smaller elements out before. Pop out the head element if its index is out of size k.

Finally, the element at head will be our answer here.

### 2. LeftMax[] & RightMax O(N) + O(N)

Cut the array into blocks with size k. Use leftMaxand RightMax[i - k + 1] to make up the window we want.

https://leetcode.com/problems/sl ... mum/discuss/65881/O(n)-solution-in-Java-with-two-simple-pass-in-the-array (One reply below with graph is much more clear than the post itself.)

### Faults:
1. **[WA]** Stupid question description. Input maybe invalid even guranteed in the description.

## 240. Search a 2D Matrix II (Medium)

> We start search the matrix from top right corner, initialize the current position to top right corner, if the target is greater than the value in current position, then the target can not be in entire row of current position because the row is sorted, if the target is less than the value in current position, then the target can not in the entire column because the column is sorted too. We can rule out one row or one column each time, so the time complexity is O(m+n).

### Faults:
1. **[WA]** Wrong while loop range.

## 241. Different Ways to Add Parentheses (Medium)

### 1. Recursion O(N^2) + O(N^2)

### 2. DP O(N^2) + O(N^2)

``` java
ArrayList<Integer>[][] rec = (ArrayList<Integer>[][]) new ArrayList[len][len];
```

# Leetcode Weekly Contest 76

## 800. Similar RGB Color (Easy)

The conversion between string, hexadecimal number and decimal number.

Two useful method in java:
1. `Integer hexNum = Integer.parseInt(st, 16);`
2. `String hexStr = Integer.toHexString(num);`

Faults:

1. **[WA]** Inadequate description about output format.
2. **[WA]** Inadequate description about output format.
3. **[WA]** Inadequate description about output format.


## 801. Minimum Swaps To Make Sequences Increasing (Medium)

An obvious dynamic programming problem. (The problem could be devided into different stages. The best solution from last stage could serve in best solution for next stage.)

u means minimum swaps if i-th elements are not swapped
s means minimum swaps if i-th elements are swapped

    u = min{c[i - 1], u[i - 1]}
    c = min{c[i - 1] + 1, u[i - 1] + 1}

**Remember to check whether the strictly increasing rule is satisfied.**


## 802. Find Eventual Safe States (Medium)

### Approach 1

Find all nodes in a cycle and nodes could walk to a cycle, delete them from answer.

There are several mature solutions to find cycles in both BFS and DFS. You should pay more attention when using a DFS approach.

### Approach 2

Start from definite safe nodes (has no outgoing edge), use reversed edges to find safe nodes connected to these node. Implemented by BFS. (Detail: https://leetcode.com/articles/find-eventual-safe-states/)

Faults:

1. **[TLE]** Not enough optimization for DFS.


## 803. Bricks Falling When Hit (Hard)

A complicated and challengable problem.

### Approach 1

BFS. (My Solution https://github.com/mintycc/Onlin ... lling_When_Hit.java)

### Approach 2

Add bricks reversely and use disjoint-set-union to maintain the combination. (Detail: https://leetcode.com/articles/bricks-falling-when-hit/)

Faults:

1. **[WA]** Even though a brick will be erased, it may drop before the erasion.
2. **[TLE]** Use one boolean array to record visited bricks.

Mar. 20th 2018 --- 6 problems

## 68. Text Justification (Hard)

String processing problem with complicated cases.

Faults:
1. **[WA]** One line forget to delete in "space == 0" part, and didn't come up with test case for such condition.
2. **[WA]** Format will be different for the last line of text.

## 71. Simplify Path (Medium)

Stack.

## 72. Edit Distance (Hard)

### Approach 1

BFS. But the time performance is so poor.

### Approach 2

O(NM) DP. f[j] means the edit distance between the first i characters of word1 and the first j characters of word2.

    f[j] = min {
        f[i - 1][j] + 1,
        f[j - 1] + 1,
        f[i - 1][j - 1] + 1,
        f[i - 1][j - 1] (if word1 == word2[j])
        }

Faults:
1. **[WA]** One line of code forgot to delete.
2. **[TLE]** Poor time performance of BFS.
3. **[TLE]** Same as above.
4. **[TLE]** Same as above.
5. **[RE]** Input may be null.

## 73. Set Matrix Zeroes (Medium)

Easy to find one solution with O(N+M) space, but a little tricky to solve it with O(1) space.

Use the first row and column as the tag for zeroes. Scan them at first and change them at last.

Faults:

1. **[WA]** If (0, 0) is zero, you don't know it comes from row or column, or it is zero from the beginning. So another two variables are need to record if the first row and column contain any zeroes.

## 74. Search a 2D Matrix (Medium)

Binary Search.

Faults:

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

## 75. Sort Colors (Medium)

### Approach 1 (2 pass)

Count the number of 0s, 1s and 2s, overwrite the array.

### Approach 2 (1 pass)

Scan the array, swap 0 to the head and 1 to tail.

### Approach 3 (1 pass O(N) O(N))

https://leetcode.com/problems/so ... with-one-pass-and-O(n)-time-and-O(n)-space

Faults:

1. **[WA]** Wrong for-loop range, there maybe no 2s.

Mar. 21st 2018 --- 7 Problems

## 76. Minimum Window Substring (Hard)

Use one HashMap to store the characters in target string, another HashMap to store the characters you got in the substring.

One queue to maintain the substring. Push next character in. Keep polling head character out if you got enough this character or it doesn't belong to target string.

Update answer when all characters are acquired.

Notice: There maybe duplicate characters in string t. In such condition, the substring you found should contain as many as characters as the target string.

Faults:

1. **[TLE]** Remember check whether queue is empty before poll, otherwise it maybe keep poll.

## 77. Combinations (Medium)

DFS. Be careful about corner cases like k = 0 or k > n.

## 78. Subsets (Medium)

Almost the same as #77.

## 79. Word Search (Medium)

DFS.

## 80. Remove Duplicates from Sorted Array II (Medium)

Use one variable to count how many time this number has appeared. If already twice then go to the next one. The same if question is "at most k times".

## 81. Search in Rotated Sorted Array II (Medium)

Binary search. Find the start of array (the smallest one) and use it as be base for index conversion. Be careful with cases like [0, 1, 2, 0, 0].

## 82. Remove Duplicates from Sorted List II (Medium)

Add one node to result if its value is different from last node or next one.

Faults:

1. **[WA]** I set the value for an empty head node to Integer.MIN_VALUE, but inputs also include this value. Better be careful for circumstances like this.

Mar. 22nd 2018 --- 7 Problems

## 84. Largest Rectangle in Histogram (Hard)

Use one stack to store rectangles. Before push one new rectangle in, pop all rectangles taller than it out, calculate the largest area at the same time.

Push another zero or minus value at last to clear the whole stack.

## 85. Maximal Rectangle (Hard)

2D version of #84. Solve this problem row by row, use the same method as #84, the height could be inheritaged from last row.

## 86. Partition List (Medium)

Another two ListNode head for classification.

## 87. Scramble String (Hard)

Recursion. But only recursion is not fast enough to pass the test. I added two HashMap, return false as long as two strings contain different characters.

However, it is still not the best solution. We repeat to check some part in the recursion, so DP could be introduced to optimize the time performance.

Faults:

1. **[WA]** There may be no swap in one subtree.
2. **[TLE]** Bare resursion is not fast enough to past the test.

## 89. Gray Code (Medium)

Write the answer in binary and look for pattern

## 90. Subsets II (Medium)

DFS. To avoid duplicates, add next[] array which points to the next distinct number's pos. If you don't choose one number, jump directly to its next. In such a way, you can always make sure you picked numbers from left to right.

## 91. Decode Ways (Medium)

DP. Be careful with '0' conditions like 10, 20 ...

Faults:

1. **[WA]** Input could be illegal like one 0.

楼主加油。我现在也基本专职刷题。要加个微信交流一下吗? srl_syh

Mar. 23rd 2018 --- 5 Problems

## 92. Reverse Linked List II (Medium)

Reverse ListNode.

## 93. Restore IP Addresses (Medium)

DFS. Mind leading zero issues.

Faults:

1. **[WA]** Leading zeroS.

## 94. Binary Tree Inorder Traversal (Medium)

Use stack to store nodes. When you pop one node for the first, push its right child in, push itself in, push its left child in. When you push one node for the second time, really pop it out and add it to the result.

## 96. Unique Bianry Search Trees (Medium)

DP.

## 98. Validate Binary Search Tree (Medium)

DFS. Collect the maximum and minimum value of each subtree, and compare them with the subtree's root.

Faults:

1. **[WA]** Integer.MAX_VALUE and Integer.MIN_VALUE appear in the input.
2. **[WA]** Same as above.
3. **[WA]** Same as above.

毒奶当 发表于 2018-3-23 09:44
楼主加油。我现在也基本专职刷题。要加个微信交流一下吗? srl_syh

不好意思要休息了才看到…… 明天加你！

Mar. 24th 2018 --- 5 Problems

## 95. Unique Binary Search Trees II (Medium)

First find the answer for i-1 nodes, then try to put one new TreeNode (val = i) in to makeup the answer for i nodes. The new node could be root's father, or the right child of nodes on the rightest side. If new node becomes node K's new right child, then make its original right child new node's left child.

## 97. Interleaving String (Hard)

DP. f[j] means the first i characters of s3 matches with the first j characters of s1 and (i - j) characters of s2.

BFS and DFS are not only feasible but also able to achieve a better time performance.

## 99. Recover Binary Search Tree (Hard)

1. Recursion is never O(1) space
2. Morris Traversal http://www.cnblogs.com/AnnieKim/ ... orristraversal.html


## 102. Binary Tree Level Order Traversal (Medium)

BFS.

## 103. Binary Tree Zigzag Level Order Traversal (Medium)

BFS. The same as #102.

Mar. 25th 2018 -- Weekly Contest 77

做Weekly Contest做到心态爆炸。估计Rating要暴跌。
别人几分钟开始出题，十几分钟有几十个人把前三题都清掉，我这里吭吭哧哧半个小时才把前三题做完。
第四题有200+人A掉，我也没做出来，一开始理解错题意，后来忽视了一条条件结果死活找不到够强力的剪枝。

教训：

• 以后做题记录时间，会做的题练习速度。
• 理解题目时候，先亲手把样例算一下。（有时候样例很糟是问题）
• 做DFS的时候多想想剪枝多练习常用处理。
  

## 804. Unique Morse Code Words (Easy)

HashSet.

## 805. Split Array With Same Average (Hard)

DFS. I didn't find strong enough optimization during the contest.

Notice that:
    (avg * B + avg * C) / (B + C) = avg

So both the two lists' average equals to the average of A.

One feasible optimization is like IDDFS, set the sum and num (sum = num * avg) of one list, try to find the answer. If no answer exists, try another range.

Faults:

1. **[WA]** Misunderstand the problem description.
1. **[WA]** x 4, test optimization.
1. **[TLE]** x 3, test optimization.

## 806. Number of Lines To Write String (Easy)

Easier than #68.

## 807. Max Increase to Keep City Skyline (Medium)

Find the largest value in one row and column.