-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathSecondStep.txt
119 lines (96 loc) · 3.12 KB
/
SecondStep.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
August 3rd:
1. Subarray Related Problem
Solution: Segment Tree, Binary Index Tree, PreFix subarray.
Problems: Subarray Sum Range Sum Query(Binary Index Tree) Maximum Sub-matrix(From 2D to 1D)
2. Merge Two sorted List Problem
Solution: Heap, Merge Sort plus Merge Sort
Problems: Merge Sorted Array, Merge K Sorted Arrays
Plus: Interval Problem
Solution: to check the boundary of different interval and change the interval or add into
the array/List
Problem: Merge Two Sorted Interval Lists, Merge K Sorted Interval Lists
3. Median Problem: (Attention !!)
Solution: Remove, Binary Search(FindKth), FindKth(K - k / 2)
Problems: Median of Two Sorted Arrays, Median of K Sorted Arrays
August 4th:
Median Problem Review:
Solution 1:
FindKth (k - k / 2) : Boundary Case [3] [4] O(log(m + n))
FindKth (Binary Search) : Boundary Case count < k !!! O(log(Range)(log(m) + log(n))
Remove Method （Unsolved)
August 5th
1. Build your own LinkedList to show when the Object showed up
Problem : LRU Cache, First Unique Number in Data Streaming
Solution: Singly List, Double List
LRU cache: LinkeHashMap
3. Write Comparator
K Closest Points
4. Top K
Heap(Priority Queue) O(nlog(k))
Problems : Top K Largest Numbers, K Closest Points,
August 6th
5. Ugly Number
6. Insert Delete Random in O(1)
Random rand = new Random()
Rand.nextInt(range)
August 7th
Permutation I & II: O(n! * length of the Array)
I just normal Permutation DFS
II remember to remove duplication values.
NQueens I & II: Worst Case < O(n!)
August 8th
WordPattern: When meet special case, remember to return O(n^2)
WordSearch: When check the added. O(n ^ 2) not sure
August 9th
Kth Smallest Number in Sorted Matrix: trick get count from up-right corner to left bottom O(nlog(k))
August 10th
Word Ladder II: BFS from end to start, DFS from start to end O(nlog(n)) ~ O(n^2)
Minimum Size Subarray Sum: O(n)
August 13th
Subsets I & II: O(x ^ n)
August 21th:
Dynamic Programming:
1. State:
Maximum/Miniumum Yes/No Count
2. Function:
Relation between different state
3. Initialization:
The start point
4. Answer:
The ending point
Rolling Array:
Fibonacci: use three integer to store the first two integers
House Robber & House Robber II:
State: f[i] the Max value from i houses ahead
Function: f[i] = A[i - 1] + max(f[i - 2] ... f[1])
initilization: f[0] = 0; f[1] = A[0]
Answer: f[n]
August 22th:
Array Dynamic Problem:
Maximal Square:
1. State:
f[I][j]: the maximum length of a square
2. Function:
f[I][j] = min(f[I - 1][j], f[I][j - 1], f[I][j]) + 1 if maxtrix[I][j] == 1 else = 0
3. Initialization:
f[0][I] = matrix[0][I]
f[I][0] = matrix[I][0]
4. Ans:
max(f[I][j])
Maximal Square 2:
August 27th:
Coins in a Line II:
State:
dp[i] 表示取i～ n - 1这些硬币时， 先手取得的最大硬币总价
Function：
sum[I] sum (I ~ n - 1)
August 28th:
Coins in a line I, II & III
From first state to the desired state:
I: from first to last to check if the last is true
II: from the last to first element to check if the first is the largest value
August 30th:
Interval Dynamic Programming Problem:
To get the max or min in a interval.
State is update through interval changes.
Large interval reply on small interval.