Leetcode刷题记录帖

Apr. 11th 2018 --- 2 Problems

## 141. Linked List Cycle (Easy)

### 1. Modify the linked list (O(N), O(1))

Set one node's value to 0 after you visited it. When you visit one node that has been visited before, that means you reached one cycle.

### 2. Two pointers with different speed (O(N), O(1))

Two pointers, one fast one slow. The fast one move two steps forward at a time and the slow one move only step. If the two pointers meet together again, which means the fast pointer must walk through the cycle.

### Faults:

1. **[WA]** There is -1 but no 0 in this list.

## 142. Linked List Cycle II (Medium)

### Two pointers with different speed + (O(N), O(1))

Based on approach 2 from problem 141.

    S             P          M              P
    |------------|---------+------------|
    |←   a   →|← b →|← (c-b) →|

S is the head of the linked list. P is the position where the cycle starts. M is the position where the fast pointer  meets the slow pointer.

The dist from S to P is a. The length of the cycle is c. The dist from P to M is b.

Because the speed of fast pointer is twice as the slow one, we have `a + b + c = 2a + 2b`. Thus, `a = c - b`. Which means if we start from S and M with the same speed, they will meet at P, the answer we want.

(Only illustrated fast pointer passed one cycle. It may cost several cycles for the two pointers to meet, but the conclusions are the same.)

### Faults:

1. **[RE]** Input node maybe null.

Itsme 发表于 2018-4-11 04:39
楼主加油！
最近也在刷题，准备今年秋天的全职:)

感谢，大家一起加油！(･ω･)ﾉ

Apr. 12th 2018 --- 5 Problems

## 143. Reorder List (Medium)

Three steps:

1. Split the list into two.
2. Reverse the second list.
3. Merge two lists together.

## 144. Binary Tree Preorder Traversal (Medium)

Stack.

## 145. Binary Tree Postorder Traversal (Hard)

Stack with some modification.

## 146. LRU Cache (Hard)

### 1. HashMap + Queue

This is my solution. Record the number of operations on the side.

Whenever you do some operation, update the element in the HashMap to show when this element was visited lately, and push this key into the queue.

When the space is not enough and you poll one key out of the queue, check whether the time stamp is the latest. If so, set the value of the key to -1.

### 2. HashMap + Double Linked List

Use HashMap to store the map from key to  node in double linked list. If you visit one node, delete it from the list (O(1) because it is a double linked list) and add it to the tail. When size is not enough, delete from the head of the list.

### 3. LinkedHashMap

https://leetcode.com/problems/lr ... mplementation:-Java

## 147. Insertion Sort List (Medium)

Linked list operation.

Apr. 13th 2018 --- 2 Problems

## 148. Sort List (Medium)

Merge sort.

### Faults:

1. **[RE]** Wrong if statement.

## 149. Max Points on a Line (Hard)

### HashMap (O(N * N), O(N))

Use gradient as the key of HashMap, enumerate the start point of the line, points with the same gradient will fall on the same line.

But after added the latest test case, double gradient will not pass. Either use BigDecimal instead, or store both x0 and y0 at the same time, which means HashMap in a HashMap.

### Faults:

1. **[WA]** x 7.

Apr. 14th 2018 --- 3 Problems

## 150. Evaluate Reverse Polish Notation (Medium)

Stack.

## 151. Reverse Words in a String (Medium)

String.trim()
String.split("\\s+")
StringBuilder

### Faults:

1. **[CE]**
2. **[CE]**
3. **[RE]**
4. **[WA]**

## 154. Find Minimum in Rotated Sorted Array II (Hard)

At lease O(N).

### Faults:

1. **[WA]** Binary search is not avaliable here.
2. **[WA]** Same as above.
3. **[WA]** Same as above.

Apr. 15th 2018 --- 4 Problems

Weekly Contest 80

## 816. Ambiguous Coordinates (Medium)

String manipulation.

### Faults:

1. **[WA]** Wrong range to add the decimal point.

## 817. Linked List Components (Medium)

HashSet + Iteration.

### Faults:

1. **[RE]** Stack overflow if recursion.

## 818. Race Car (Hard)

https://leetcode.com/problems/race-car/solution/

Tricks:

    Arrays.fill(dp, Integer.MAX_VALUE);
    int k = 32 - Integer.numberOfLeadingZeros(t);

## 819. Most Common Word (Easy)

HashMap.

Apr. 16th 2018 --- 2 Problems

## 162. Find Peak Element (Medium)

Binary Search.

## 164. Maximum Gap (Hard)

Bucket sort.

https://leetcode.com/problems/ma ... -with-explanation-O(N)-time-and-space

Apr. 17th 2018 --- 2 Problems

## 165. Compare Version Numbers (Medium)

String.split("\\.");

### Faults:

1. **[WA]** Different read the question description carefully.

## 166. Fraction to Recurring Decimal (Medium)

Use a hashtable to record where the remain appeared.

This problem's test cases are quite strong.

### Faults:

1. **[WA]** Input integer may be negative.
2. **[WA]** Answer maybe zero.
3. **[WA]** Input value maybe Integer.MIN_VALUE which could not be stored in an integer if you transfer it to positive.

Apr. 18th 2018 --- 2 Problems

## 173. Binary Search Tree Iterator (Medium)

Use one stack to store the TreeNodes. First push the root and all its left children down to the bottom into to the stack. Every time you pop one element, push all the left children of its right child into the stack. This could make sure the length of stack will not surpass O(h).

## 174. Dungeon Game (Hard)

### 1. DP

### 2. Binary Search + DP

### Faults:

1. **[WA]** Knight may not survive the first block.

Apr. 19th 2018 --- 3 Problems

## 177. Nth Highest Salary (Medium)

    SELECT DISTINCT Salary FROM Employee ORDER BY Salary DESC LIMIT M, 1

## 178. Rank Scores (Medium)

    SELECT
        Score,
        (SELECT COUNT(DISTINCT Score) FROM Scores WHERE Score >= s.Score) Rank
    FROM Scores s
    ORDER BY Score DESC

## 180. Consecutive Numbers (Medium)

    SELECT DISTINCT l1.Num AS ConsecutiveNums FROM Logs l1, Logs l2, Logs l3
    WHERE l1.Id = l2.Id - 1 AND l2.Id = l3.Id - 1
    AND l1.Num = l2.Num AND l2.Num = l3.Num