Leetcode刷题记录帖

肥宅快乐水 发表于 2018-7-15 02:06
加油加油， 喜欢看你写的分析。

最近在纠结零度算不算真正的肥宅快乐水233

Jul. 15th 2018 --- 4 Problems

Weekly Contest 93

## 868. Binary Gap (Easy)

Nothing to say here.

## 869. Reordered Power of 2 (Medium)

Enumerate the power of 2 with the same length as input, then check if they have the same digits.

## 870. Advantage Shuffle (Medium)

Greedy solution.

Sort array A and B seperately. For each element in B, find the smallest possible element in A which is larger.

## 871. Minimum Number of Refueling Stops (Hard)

### DP O(N^3)

`f[a][k] = max{f[b][k - 1] + fuel - dist}`, `f[a][k]` means we refuels at station a and we have refueled k times in total. Our last stop is station b.

### DP O(N^2)

`f[a][k][0] = f[a-1][k][0] or f[a-1][k][1] - dist`, `f[a][k][1] = f[a-1][k-1][0] or f[a-1][k][1] + fuel - dist`

### Priority Queue (NlogN)

We first dont refuel at any stop but push them into heap. When out fuel is not enough to get to the next stop, add the stop we have visited with the largest fuel into our answer.

### Faults:
1. **[TLE]** O(N^3) is not fast enough to pass.

Jul. 24th 2018 --- 1 Problem

## 363. Max Sum of Rectangle No Larger Than K (Hard)

As long as row numbers are much larger than column, we can enumerate the staring and ending column index of such rectangles. Then the sum of rectangle will become sum of 1-D array.

The problem is then transferred into: for index i, finding index j such that prefix sum of i minus prefix sum of j is the largest smaller or equal to k. For such index i, we can to find the smallest sum(j) that `sum(j) >= sum(i) - k`. We can use one TreeSet and its method `TreeSet.ceiling(num)` to find this sum(j).

Jul. 25th 2018 --- 2 Problems

## 406. Queue Reconstruction by Height (Medium)

Sort elements with height as the first keyword and k as the second keyword. Then always try to insert the element a[j] to position a[j].k. If such place has already been taken, then move forward.

## 407. Trapping Rain Water II (Hard)

Priority Queue.

The heap holds elements with their position and the height of water they can hold. Whenever you pop out the heap top `cur`, try to visit the elements next to it that has not been visited. If the neighbour's height is larger than `cur.hold`, then the neighbour's `hold` is its own height. Otherwise, its `hold` equals to `cur.hold` (becaused we have already visited all paths with a less hold, so `cur.hold` is the least `hold` path it could be reached).

### Faults:
1. **[RE]** Input matrix maybe empty.

Jul. 26th 2018 --- 2 Problems

## 365. Water and Jug Problem (Medium)

### 1. BFS: Enumerate Jug X and Y Seperately (TLE)

### 2. BFS: Enumerate the Sum of Jug X and Y

### 3. Math Approach

`ax + by = kd` which means all the answers could be made from x and y must be  multiple of d, the GCD of x and y.

### Faults:

1. **[TLE]** Solution 1 turns out TLE.

## 410. Split Array Largest Sum (Hard)

Dynamic programming.

`f[a][k]` means the minimum value of largest sum of the k subarrays until position a. Calculate the prefix sum beforehand, and you will get the equation:
```
f[a][k] = Min{f[c][k - 1] + sum[a] - sum[c]} (c < a)
```

### Faults
1.**[WA]** The `Integer.MAX_VALUE` will appear in the input.

Jul. 28th 2018 --- 2 Problems

## 368. Largest Divisible Subset (Medium)

Sort the array and then use quadratic DP.

## 372. Super Pow (Medium)

High precision and fast modular exponentiation.

Jul. 22nd/29th 2018 --- 8 Problems

Weekly Contest 94

## 872. Leaf-Similar Trees (Easy)

DFS.

## 873. Length of Longest Fibonacci Subsequence (Medium)

DP + HashMap.

## 874. Walking Robot Simulation (Medium)

Simulation + HashMap.

### Faults:
1. **[WA]** The problem wants the farthest distance from the origin, not the final position.

## 875. Koko Eating Bananas (Medium)

Binary search.


Weekly Contest 95

## 876. Middle of the Linked List (Easy)

Two node, one fast and one slow.

## 877. Stone Game (Medium)

Quadratic DP. Or just return true.

## 878. Nth Magical Number (Hard)

### Enumerate the madical number one by one (TLE)

### LCM

First calculate the LCM of A and B, and figure out k, the number of magical numbers in the range of LCM. Divide N by k, then we need that much LCM in the ans. Mod N by k, and enumerate the remaining part one by one, add that to the answer.

### Faults:
1. **[TLE]** Solution 1 will TLE.

## 879. Profitable Schemes (Hard)

Classic backpack problem. Regard number of people and profit as the two dimension volume limitation.

mintyc 发表于 2018-4-12 22:49
Apr. 12th 2018 --- 5 Problems

## 143. Reorder List (Medium)

146用c++的话写起来会快很多

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)

刚看到楼主的帖子 楼主现在在哪儿工作呀