Leetcode刷题记录帖

joyrich 发表于 2018-6-2 02:20
这样的打卡真的会有帮助！

谢谢你！一起加油！╭(′▽`)╭(′▽`)╯

Jun. 2nd 2018 --- 1 Problem

## 327. Count of Range Sum (Hard)

Obviously, we first transfer the array into prefix sum array sum[]. Then what we want to find here is two index i, j (i < j) in sum[] such that sum[j] - sum[i] is in the required range.

We solve this problem by merge sort.

To merge sort sum[l, r], we first merge sort recursively the left half sum[l, mid] and right half sum[mid, r]. Then we need to count pair i, j than cross mid, which means i fall in [l, mid) and j falls in [mid, r). We only need to count such pairs because pairs with i, j within the same region have been counted when merge sorting each half.

After count the pairs, merge left and right half together.

### Faults:

1. **[WA]** Sum may be long type.
2. **[TLE]** It will cost too much time and memory if you new a whole array during merging. Just new the part of array you need.

Jun. 3rd 2018 --- 4 Problems

Weekly Contest 87

## 844. Backspace String Compare (Easy)

Use a stack for the two strings, pop the top out when you run into backspaces.

## 845. Longest Mountain in Array (Medium)

For each element, calculate the longest ascending subarray on its left side and right side, then combine them together.

## 846. Hand of Straights (Medium)

Use the sorted array to search what's the start of next group and hashmap to check if you still get some number left.

## 847. Shortest Path Visiting All Nodes (Hard)

State compression + dynamic programming.

f[status][pos] means the least step to achieve status `status` with ending at node `pos`. How we describe the whole status in an integer? Notice than there are at most 12 nodes in the test cases. We could use each bit of the integer to show whether one node has been visited. Then an integer with 12 bits is enough for show all of the status.

f[status][pos] may comes from f[status][posPre] or f[statusPre][posPre]. `posPre` and `pos` are connected and `statusPre = status xor (1 << pos)` which is the status than node `pos` has not been visited.

Notice than you may revisit node within the same status which means the f[status] array maybe updated in different directions. The solution is keep this update loop until no update was made.

Jun. 4th 2018 --- 1 Problem

## 328. Odd Even Linked List (Medium)

Use two linked list head to store odd list nodes and even ones seperately, then combine them together.

Jun 5th 2018 --- 1 Problem

## 329. Longest Increasing Path in a Matrix (Hard)

### 1. Memory Search O(NM)

But have the risk of stack overflow.

### 2. Dynamic Programming O(NM*log(NM))

Sort the elements and then do DP from the least to the largest.

### Faults:

1. **[RE]** `nums[i * col + j]` when you calculate the index of `matrix[i][j]` in 1-D array.

Jun. 6th 2018 --- 1 Problem

## 331. Verify Preorder Serialization of a Binary Tree (Medium)

Simulate the process by a stack or one integer.

Notice that the tree maybe null.

Jun 7th 2018 --- 1 Problem

## 330. Patching Array (Hard)

We use one integer `found`, `found = i` indicates that 1 to i could all be made up. Then the next number we want to find is `found + 1`.

The next element in `nums[]` is `k` (`nums[]` is sorted), if `k <= found + 1`, we could have 1 to `found + k` all be made up. Otherwise, we need to add `found + 1` into the group, then the range we could make up will be 1 to `2 * found + 1`.

Why `found + 1`? If larger than `found + 1`, we still need one integer for `found + 1`. If less than `found + 1`, the range we get after insertion will be less.

Jun. 8th 2018 --- 1 Problem

## 332. Reconstruct Itinerary (Medium)

What we need to do here is actually find the "Euler Path".

We use a stack to find euler path. If the node at the top of stack has some edge that we have not visited, push the other end in. Otherwise, pop the top out, and push it into the answer list.

Reverse the answer list, then you will get the path we want.

Jun. 9th 2018 --- 1 Problem

## 334. Increasing Triplet Subsequence (Medium)

We use two variables to store the smallest element and second smallest during scanning. Update the `second` if element is bigger than `first` and smaller than `second`. But if element is smaller the `first`, we only update the `first`.

This is because we must make sure `first` appears before `second`, we will not update `second` until some new suitable element appears after new `first`.

Jun. 10th 2018 --- 4 Problem

Weekly Contest 88

## 848. Shifting Letters (Medium)

Shift the characters.

### Faults:
1. **[TLE]** You could not shift one character again and agian,  you should add all shifts together and do the shift in one time.
2. **[RE]** The shift distance itself maybe too large, you should mod 26 during the adding.

## 849. Maximize Distance to Closest Person (Easy)

Scan forwards and backwards.

## 850. Rectangle Area II (Hard)

Scan line.

Scan the area vertically. For the y-axis that some rectangles appear or disappear, calculate the length of x-axis that has been covered. The length of covered x-axis multiples the y-axis without rectangle appears or disappears, will be the area in this part.

## 851. Loud and Rich (Medium)

BFS.