Leetcode刷题记录帖

笔记的做法学习了！(ง •̀_•́)ง
一起加油！

Estheroy 发表于 2018-6-23 02:03
笔记的做法学习了！(ง •̀_•́)ง
一起加油！

嘿嘿随便记记 主要还是为了复习的时候 能快点回忆起思路和要点

Jun. 23rd 2018 ---- 4 Problems

Weekly Contest 4

## 396. Rotate Function (Medium)

If you write down the process for several steps, you will find the pattern.
```
    0 1 2 3 4
    1 2 3 4 0
    2 3 4 0 1
    3 4 0 1 2
    ...
```
```
F(p) = F(p - 1) + sum - n * A(n - p)
```

## 397. Integer Replacement (Medium)

Change the number `n` to binary. Then what we need to do now is to transfer this binary string to 1.

We do this in three steps:
1. If the last bit is 0, divide number `n` by 2;
2. If the last bit is 1 and the second last is also 1, add `n` by 1;
3. If the last bit is 1 but the second last is 0, minus `n` by 1.

### Faults:
1. **[WA]** Number 3 is very special here.
2. **[RE]** The number maybe larger than `Integer.MAX_VALUE` after add one.

## 398. Random Pick Index (Medium)

Binary search the interval and random pick one from them.

### Faults:
1. **[RE]** Out of range may happen if you override compare function by `a.val - b.val`.

## 399. Evaluate Division (Medium)

The equations are actually path and the queries are for the distance between two nodes.

Use HashMap to store the paths and DFS to calculate the distance.

Jun. 24th 2018 --- 4 Problems

Weekly Contest 90

## 856. Score of Parentheses (Medium)

2-D for-loop.
`f[p][q]` stands for the value from pos p to pos q. Its value is larger than 0 if it is valid, less than 0 if not.

## 857. Minimum Cost to Hire K Workers (Hard)

First we define ratio = wage / quality.

What we want to achieve here is to find K workers so than the product of largest ratio and quality sum is the smallest.

We can sort all workers by their ratios, then enumerate the ratio from smallest to largest. If the ratio now is ratio[p], then we need to find the smallest k qualities from 1-p.

When p increases, how to find the k smallest qualities quickly? Use PriorityQueue.

## 858. Mirror Reflection (Medium)

If the light hits on the wall between 1 and 2, it will reflect back. But imagine instead let the light reflect, we extend the room infinitely. Then the width that light will pass will be the lcm of p and q.

## 859. Buddy Strings (Easy)

Calculate different letters and check if they are the same.

Jul. 2nd 2018 --- 4 Problems

Weekly Contest 91

## 860. Lemonade Change (Easy)

Greedy problem. Each time use the largest possible bill for change.

## 861. Score After Flipping Matrix (Medium)

The leftest column is the most significant. The sum of all bits after the first bit is less than the one bit.

So we must make sure the first bit of each row is 1. The we check column by column to see whether flip this column will bring us more 1s.

## 862. Shortest Subarray with Sum at Least K (Hard)

As usual, we transfer then subarray problem to 'find two prefix sum'. Now the problem is finding two nearest index such that the difference between their prefix sum is larger than K.

We use a stack to maintain an ascending array while scaning the values. Once we have a index with a smaller prefix sum, the index before with larger prefix sum will never be our best answer. Once we got this ascending array, we could use binary search to find the best answer.

## 863. All Nodes Distance K in Binary Tree (Medium)

Notice that n is very small (n <= 500), we could use DFS or BFS to find the distance of all nodes directly.

Jul. 11th 2018 --- 1 Problem

## 864. Random Pick with Blacklist (Hard)

Suppose the range is [0, n) and m of them are in the black list. We use a map to map these m numbers to the last m numbers in n. The produce the random number in range [0, n - m).

Jul. 8th 2018 --- 4 Problems

Weekly Contest 92

## 865. Shortest Path to Get All Keys (Hard)

BFS with Status Compression.

## 866. Smallest Subtree with all the Deepest Nodes (Medium)

Two DFS, one to calculate the depth and another to return subtrees.

## 867. Prime Palindrome (Medium)

Enumerate length of the number, then enumerate the first half of it. Produce the whole number and check whether it is a prime.

### Faults:
1. **[WA]** Input maybe 1.
1. **[WA]** Input maybe 2.

## 868. Transpose Matrix (Easy)

For-loop.

Jul. 13th 2018 --- 1 Problem

## 355. Design Twitter (Medium)

One list to store all the tweets.
One `Map<Integer, Set>` to store the maps from follower to followee.
Scan the tweets list backwards and check if the author of that tweet is followed by the user in query.
Remember to check if the user exists all the time.

### Faults:
1. **[WA]** User may unfollow himself in the input but his own tweet should always be showed.

Jul. 14th 2018 --- 1 Problem

## 357. Count Numbers with Unique Digits (Medium)

Permutation and combination.

### Faults:

1. **[WA]** The answer should be one when n equals zero.

加油加油， 喜欢看你写的分析。