Leetcode刷题记录帖

Jun. 13th 2018 --- 3 Problems

## 335. Self Crossing (Hard)

### 1. Queue and Intersect O(n) + O(1)

Use queue to store the six newest edges and use cross to judge if the newly added one intersects with any of them.

### 2. Improvement O(n) + O(1)

Don't use queue and cross anymore, just use the length of edges to judge.

### Faults:

1. **[WA]** The edges may run to (0, 0) again.

## 386. Lexicographical Numbers (Medium)

DFS.

## 388. Longest Absolute File Path (Medium)

Use a stack to store the structure.

Learn how to handle '\n' '\t' and '\\' in java.

### Faults:
1. **[WA]** The input is so disgusting that it mixed '\t' with "    ". And sometimes there maybe "    " in directory name.

Jun. 14th 2018 --- 2 Problems

## 390. Elimination Game (Medium)

Record the head position. Head position changes only when it is the odd turn or even turn but odd number of numbers left.

Move head position for `shift`. `shift` doubles every turn.

## 391. Perfect Rectangle (Hard)

I learnt so much from this problem !

In order to check if it is perfectly covered, we need to make sure:
1. The sum of all rectangles' area equals the covered area.
2. No rectangles are intersected.

The first condition is easy to check. To check the second condition, we have three solutions:

### Scan O(N * N)

Enumerate two rectangles are check if they are intersected.

### Calculate the corners O(N)

If the area is perfectly covered, then evey corner in this area is covered by even times.
We can use a set to record times. But how could we know two corner object equals? We could store their values in string.

### Scan line O(N * log(N))

Split each rectangle into two parts: the starting part and ending part. Sort all of them according to x value, insert the rectangle into treeset when you meet the starting part and remove when meet the ending part. If the y values of two rectangles intersect with each other, which means the rectangles themself intersect.

#### Why TreeSet?

TreeSet is like set but with order. We can compare two elements during adding.

#### Comparison method violates its general contract!

In java7, TimSort is used in `Arrays.sort()`. There are three must be obeyed:

> 1. The implementor must ensure that sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and y.

> 2. The implementor must also ensure that the relation is transitive: ((compare(x, y)>0) && (compare(y, z)>0)) implies compare(x, z)>0.

> 3. Finally, the implementor must ensure that compare(x, y)==0 implies that sgn(compare(x, z))==sgn(compare(y, z)) for all z.

### Faults:
1. **[TLE]** Scan is not fast enough;
2. **[RE]** Wrong comparator.
3. **[WA]** Wrong ry calculation.

Jun. 15th 2018 --- 2 Problems

## 336. Palindrome Pairs (Hard)

### Enumerate two strings and test the combination O(N*N*L)

### Enumerate one string and length of the other string O(N*L*L)

### Faults:

1. **[TLE]** Solution 1 is not fast enough.
2. **[WA]** There maybe empty string in the input.

## 337. House Robber III (Medium)

TreeDP.

Jun. 16th 2018 --- 1 Problem

## 338. Counting Bits (Medium)

All the bits from (1 << k) to (1 << (k + 1) - 1) are the same as the bits from 0 to (1 << k - 1) except the highest bit.

Jun. 17th 2018 --- 4 Problems

Weekly Contest 89

## 852. Peak Index in a Mountain Array (Easy)

Scan.

## 853. Car Fleet (Medium)

Calculate the final time of each car's arrival ignoring the car fleet condition. Then find the increasing sequence in the time table. Only when the arrival time is larger the largest time arrived, a new car fleet will start.

## 854. K-Similar Strings (Hard)

Iteritive Deepening DFS. Enumerate how many swap should be taken at least, then DFS within this limitation.

## 855. Exam Room (Medium)

The problem description doesn't hold water because even though the range of n is 10^4 which requires a O(n * log(n)) solution, the actual range is 10^3 and one can pass with a O(n * n) solution.

### TreeSet O(n) Insert and O(log(n)) Remove

Scan all existed students while inserting and use treeset's remove while leaving.

### PriorityQueue without Map O(log(n)) Insert and O(n) Remove

Sort the gaps in the PriorityQueue. Split one gap when inserting one student and merge two gaps together when one student leaves.

The remove process here is O(n) because we don't have one map here the default remove in PriorityQueue is O(n).

### PriorityQueue with Map O(log(n)) Insert and O(log(n)) Remove

One HaspMap to map from the gap to its position in the PriorityQueue. Obviously we couldn't use the PriorityQueue provided by Java anymore and need to write by ourselves.

Jun. 18th 2018 --- 1 Problem

## 341. Flatten Nested List Iterator (Medium)

Use stack to store elements. When list appears, the list should be opened to take out integer elements. As long as stack is not empty, there will be next element.

### Faults:
1. **[RE]** As there are empty lists, you should open the list before next `hasNext()` inquiry.

Jun. 19th 2018 --- 2 Problems

## 343. Integer Break (Medium)

Dynamic programming. The classic backpack problem.

## 347. Top K Frequent Elements (Medium)

The problems asks for a O(n) solution.

The first step is all the same: calculate how many times each number appears which cost O(n).

Sorting them and getting the top K ones is the key point here. If we sort it normally then the complexity will be O(nlogn). But we can use bucket sort here since the largest times here will be `nums.length`.

Jun. 20th 2018 --- 1 Problem

## 352. Data Stream as Disjoint Intervals (Hard)

Union-Find.

Every numbers' father points to itself at first. When some number `val` is taken, point its father to `val + 1`.

Start every number `val`, find its final father `fa`. If `fa == val` then it's empty. Else `[val, fa - 1]` will be an interval.

Jun. 21st 2018 --- 4 Problem

Weekly Contest 3

## 392. Is Subsequence (Medium)

One easy dynamic programming problem.

One array `match[]`, `match[j] = k` means `s[0:k] could be the subsequence of t[0:j]`.

`match[j] = match[j - 1] + 1` if `t[j] == s[match[j - 1] + 1]` else `match[j] = match[j - 1]`.

### Faults:

1. **[RE]** S and T could be empty string.

## 393. UTF-8 Validation (Medium)

String manipulation.

### Faults:

1. **[WA]** The input array may contain more than one character.

## 394. Decode String (Medium)

Almost the same as #224.

### Faults:

1. **[WA]** The inputs include not only lower cases but also upper cases.

## 395. Longest Substring with At Least K Repeating Characters (Medium)

The two ends of the answer must be letters appears less than k times in some substring. So we first mark out all letters with apperance less than k times in string s and check the substrings between. If it is illegal, then allow it to compete for the best answer. If not, check the substrings of it recursively.

### Faults:

1. **[WA]** Forget to check the substring between last marked letter and `end`.

Jun. 22nd 2018 --- 1 Problem

## 354. Russian Doll Envelopes (Hard)

Sort the array accordig to widths increasingly then according to heights decreasingly. Then the problem is transfered into "finding the longest increasing subsequence" on heights dimension.

### Improvements:
1. `Arrays.sort(envelopes, new Comparator<int[]>(){});`
2. `Arrays.binarySearch();`