Leetcode刷题记录帖

Apr. 28th 2018 --- 1 Problem

## 216. Combination Sum III (Medium)

Recursion.

Apr. 29th 2018 --- 4 Problems

## 824. Goat Latin (Easy)

StringBuilder.

## 825. Friends Of Appropriate Ages (Medium)

### 1. Scan O(N * N)
### 2. Queue Optimization O(N)

Special treatment for the same ages.

## 826. Most Profit Assigning Work (Medium)

Sort + Delete Duplicates + Binary Search.

## 827. Making A Large Island (Medium)

Floodfill, dye the islands with different colors, use one map to record the size of each island, then enumerate the block to change.

Apr. 30th 2018 --- 1 Problem

## 461. Hamming Distance (Medium)

Bit Manipulation.

May 1st 2018 --- 1 Problem

## 218. The Skyline Problem (Hard)

The turn points appear only when one building starts or ends. So we split each building into two turn points. And use priority queue to maintain the highest height. When one building start, push it into heap. When the heap top building has already ended, pop it out.

May 2nd 2018 --- 4 Problems

## 220. Contains Duplicate III (Medium)

### TreeSet O(NlogN)

### Bucket Sort O(N)

### Faults:
1. **[WA]** The divider should also be long type, otherwise error will appear.

## 221. Maximal Square (Medium)

Dynamic Programming.

## 222. Count Complete Tree Nodes (Medium)

### Iteration O(N)

Somtimes iteration will be faster than recursion, and somtimes just the opposite.

### depthLeft & depthRight O(logN * logN)

If one tree is full binary tree (depthLeft == depthRight, which are all the way down to left and all the way down to right), return ((1 << depth) + 1). Else return countNodes(leftChild) + countNodes(rightChild) + 1.

## 223. Rectangle Area (Medium)

The sum of two rectangles minus the overlap part.

May 3rd 2018 --- 5 Problems

## 224. Basic Calculator (Hard)

Convert the infix expression to postfix expression (with stack), then calculate the value of this postfix expression.

This approach maybe complicated, but it could achieve a much more powerful calculator in a practical way.

## 227. Basic Calculator II (Medium)

Same as #224.

## 228. Summary Ranges (Medium)

Scan.

## 229. Majority Element II (Medium)

Boyer-Moore Majority Vote

https://leetcode.com/problems/ma ... -and-my-elaboration

## 230. Kth Smallest Element in a BST (Medium)

### 1. count nodes of each subtree
### 2. recursion
### 3. iteration

May 4th 2018 --- 1 Problem

## 233. Number of Digit One (Hard)

Count the ones bit by bit.

### Faults:
1. **[WA]** Will not be negative necessarilly after overflow.

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];
```

May 6th 2018 --- 4 Problems

## 828. Unique Letter String (Hard)

For character ch, find the nearest same letter before it and after it, then all substrings between these two letters will have ch as unique letter. How to calculate it? Multiply the length on left and right together.

## 829. Consecutive Numbers Sum (Medium)

Actually we need to find x, y such that x * y == N.

## 830. Positions of Large Groups (Easy)

Scan.

## 831. Masking Personal Information (Medium)

String processing.

May 7th 2018 --- 3 Problems

## 260. Single Number III (Medium)

Amazing solution!

https://leetcode.com/problems/si ... /Accepted-C++Java-O(n)-time-O(1)-space-Easy-Solution-with-Detail-Explanations

## 262. Trips and Users (Hard)

``` sql
SELECT Request_at as Day,
       ROUND(COUNT(IF(Status != 'completed', TRUE, NULL)) / COUNT(*), 2) AS 'Cancellation Rate'
FROM Trips
WHERE (Request_at BETWEEN '2013-10-01' AND '2013-10-03')
      AND Client_id NOT IN (SELECT Users_Id FROM Users WHERE Banned = 'Yes')
GROUP BY Request_at;
```

## 264. Ugly Number II (Medium)

Hold all ugly numbers we got in a list. Use three different pointers for 2, 3 and 5 point to the list seperately. Every time add min{ugly[2] * 2, ugly[3] * 3, ugly[5] * 5} to the list and update these pointers.