Skip to content

Commit 9752679

Browse files
awangdevawangdev
committed
H
1 parent ed3ac82 commit 9752679

30 files changed

Lines changed: 2189 additions & 936 deletions

‎Java/2 Sum.java‎

Lines changed: 10 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -1,15 +1,17 @@
11
E
2-
1516438794
2+
1528356671
33
tags: Array, Hash Table
44

5-
tutorial:https://www.youtube.com/watch?v=P8zBxoVY1oI&feature=youtu.be
5+
#### HashMap<value, index>
6+
- 相对暴力简洁: 找到一个value, 存一个index
7+
- 若在HashMap里面 match 到结果, 就return HashMap里存的index.
8+
- O(n) space && time.
69

7-
解法1：相对暴力简洁, HashMap<value, index>，找到一个value, 存一个; 若在HashMap里面 match 到结果, 就return HashMap里存的index. O(n) space && time.
8-
9-
解法2：Sort array, two pointer 前后++,--搜索。Sort 用时O(nlogn).
10-
1. 第一步 two pointer 找 value.
11-
2. 注意，要利用额外的空间保留original array， 用来时候找index. (此处不能用HashMap，因为以value 为key，但value可能重复)
12-
O(n) space, O(nlogn) time.
10+
#### Sort array, two pointer
11+
- 前后++, --搜索. Sort 用时O(nlogn).
12+
- 1. 第一步 two pointer 找 value.
13+
- 2. 注意，要利用额外的空间保留original array， 用来时候找index. (此处不能用HashMap，因为以value 为key，但value可能重复)
14+
- O(n) space, O(nlogn) time.
1315

1416

1517
```

‎Java/Count of Range Sum.java‎

Lines changed: 105 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,105 @@
1+
H
2+
1528434667
3+
tags: Divide and Conquer, Merge Sort, BST, PreSum
4+
5+
TODO: Write the code + merge function
6+
7+
#### Divide and Conquer + PreSum + MergeSort
8+
- 算法非常厉害就是了: 先做presum[], 那么 sum range [i,j] 就等于是preSum[j+1] - preSum[i]
9+
- 分治: 考虑[start, mid] range里面的结果, 再考虑[mid, end] range里面的结果. (分开来 mergeSort)
10+
- 最后考虑[low,high]总体的结果
11+
- 小技巧: PreSum 做成了 (n + 1) length, 那么求range sum [i,j] 就可以简化成 preSum[j] - preSum[i]
12+
- NOTE: should write merge() function, but that is minor, just use `Arrays.sort(nums, start, end)`, OJ passed
13+
- Every mergeSort() has a for loop => O(n log n)
14+
15+
##### 如何 count range?
16+
- 这里比较特别的一个做法: 找一个 [low, mid]里面的i, mid 之后的preSum作比较 (解释源自: https://blog.csdn.net/qq508618087/article/details/51435944)
17+
- 即在右边数组找到两个边界, 设为`m, n`,
18+
- 其中m是在右边数组中第一个使得`sum[m] - sum[i] >= lower`的位置,
19+
- n是第一个使得`sum[n] - sum[i] > upper`的位置,
20+
- 这样`n-m`就是与左边元素i所构成的位于`[lower, upper]`范围的区间个数.
21+
22+
##### 神奇的重点: 为什么要 merge and sort
23+
- 边界[lower, higher] 在 sorted array 好作比较, 一旦国界, 就可以停止计算, 减少不必要计算.
24+
- 上面这个n,m的做法可行的前提: preSum[]里面前后两个 range[low, mid], [mid, high]已经sorted了
25+
- 也就是说, 在recursively mergeSort()的时候, 真的需要merge sorted 2 partitions
26+
- 也许会问: 能不能sort呢, sort不久打乱了顺序? 对,打乱的是preSum[]的顺序.
27+
- 但是不要紧: 很巧妙的, 分治的时候, 前半段/后半段 都在原顺序保留的情况下 分开process完了, 最后才merge
28+
- 在做m,n 的range的时候, 原理如下, 比如preSum被分成这么两段: `[A,B,C]`, `[D,E,F]`
29+
- 每一个preSum value `A` 在跟 preSum[i] 作比较的时候 `A - preSum < lower`, 都是单一作比较, 不牵扯到 B, C
30+
- 因此, `[A, B, C]` 是否保留一开始 preSum的顺序在此时不重要
31+
- 此时最重要的是, `[A,B,C]`以及排序好, 那么在于 `lower` boundary 作比较的时候, 一旦过界, 就可以停止计算(减少不必要的计算)
32+
33+
34+
#### BST
35+
- TODO?
36+
37+
```
38+
/*
39+
Given an integer array nums, return the number of range sums
40+
that lie in [lower, upper] inclusive.
41+
42+
Range sum S(i, j) is defined as the sum of the elements in nums
43+
between indices i and j (i ≤ j), inclusive.
44+
45+
Note:
46+
A naive algorithm of O(n2) is trivial. You MUST do better than that.
47+
48+
Example:
49+
50+
Input: nums = [-2,5,-1], lower = -2, upper = 2,
51+
Output: 3
52+
Explanation: The three ranges are : [0,0], [2,2], [0,2] and their respective sums are: -2, -1, 2.
53+
*/
54+
55+
class Solution {
56+
public int countRangeSum(int[] nums, int lower, int upper) {
57+
// edge case
58+
if (nums == null || nums.length <= 0) {
59+
return 0;
60+
}
61+
// mergeSort()
62+
long[] preSum = calcPreSum(nums);
63+
64+
return mergeSort(preSum, lower, upper, 0, preSum.length);
65+
}
66+
67+
private int mergeSort(long[] preSum, int lower, int upper, int start, int end) {
68+
if (start + 1 >= end) {
69+
return 0;
70+
}
71+
int mid = (start + end) / 2, m = mid, n = mid, count = 0;
72+
73+
// sort two sides
74+
count += mergeSort(preSum, lower, upper, start, mid);
75+
count += mergeSort(preSum, lower, upper, mid, end);
76+
77+
// calculate count in range [m, n]
78+
for (int i = start; i < mid; i++) {
79+
while (m < end && preSum[m] - preSum[i] < lower) {
80+
m++;
81+
}
82+
while (n < end && preSum[n] - preSum[i] <= upper) {
83+
n++;
84+
}
85+
count += n - m;
86+
}
87+
88+
// merge two list for range [start, end]
89+
Arrays.sort(preSum, start, end);
90+
//merge(preSum, start, mid - 1, end - 1); SHOULD use a merge function
91+
return count;
92+
}
93+
94+
private long[] calcPreSum(int[] nums) {
95+
long[] preSum = new long[nums.length + 1];
96+
for (int i = 1; i < preSum.length; i++) {
97+
preSum[i] = preSum[i - 1] + nums[i - 1];
98+
}
99+
return preSum;
100+
}
101+
}
102+
103+
104+
105+
```

‎Java/K Empty Slots.java‎

Lines changed: 116 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,116 @@
1+
H
2+
1528420589
3+
tags: Array, BST, TreeSet
4+
5+
题目解析后: find 2 number, that: 1. k slots between the 2 number, 2. no slots taken between the two number.
6+
7+
#### BST
8+
- BST structure not given, use TreeSet to build BST with each node
9+
- Every time find last/next inorder element
10+
- `treeSet.lower(x)`, `treeSet.higher(x)`
11+
- 一旦位置相隔(k + 1), 就满足题目条件
12+
- O(nlogn), good enough
13+
14+
#### Track slots of days
15+
- Reverse the array, save days index into days[], where the new index is slot.
16+
- days[i]: at slot i, which day a flower will be planted
17+
- O(n)
18+
- Needs to understand: http://www.cnblogs.com/grandyang/p/8415880.html
19+
20+
```
21+
/*
22+
There is a garden with N slots. In each slot, there is a flower.
23+
The N flowers will bloom one by one in N days. In each day,
24+
there will be exactly one flower blooming and it will be in the status of blooming since then.
25+
26+
Given an array flowers consists of number from 1 to N.
27+
Each number in the array represents the place where the flower will open in that day.
28+
29+
For example, flowers[i] = x means that the unique flower that blooms at day i will be at position x,
30+
where i and x will be in the range from 1 to N.
31+
32+
Also given an integer k, you need to output in which day there exists two flowers in the status of blooming,
33+
and also the number of flowers between them is k and these flowers are not blooming.
34+
35+
If there isn't such day, output -1.
36+
37+
Example 1:
38+
Input:
39+
flowers: [1,3,2]
40+
k: 1
41+
Output: 2
42+
Explanation: In the second day, the first and the third flower have become blooming.
43+
Example 2:
44+
Input:
45+
flowers: [1,2,3]
46+
k: 1
47+
Output: -1
48+
Note:
49+
The given array will be in the range [1, 20000].
50+
51+
*/
52+
53+
/*
54+
Thoughts:
55+
Goal is to find 2 number, that is k distance from the other, and no nodes between them.
56+
- Build Binary Search Tree using flow position from flowers[], insert node each day
57+
- Ingest iteratively and check if there is inorder node that has value diff of (k+1)
58+
- example: [1, 100, 50, 20, 3, 2] => in BST, 1 and 3 are consecutive in inorder sequence, valid.
59+
NOTE: When BST not given, just use TreeSet: treeSet.add(x), treeSet.lower(x), treeSet.higher(x)
60+
Time, O(nlogn)
61+
*/
62+
63+
class Solution {
64+
public int kEmptySlots(int[] flowers, int k) {
65+
// check edge case
66+
if (flowers == null || flowers.length == 0 || k < 0) {
67+
return - 1;
68+
}
69+
70+
// build binary tree with each node
71+
TreeSet<Integer> treeSet = new TreeSet<>();
72+
for (int i = 0; i < flowers.length; i++) {
73+
int num = flowers[i];
74+
treeSet.add(num);
75+
Integer lower = treeSet.lower(num);
76+
Integer higher = treeSet.higher(num);
77+
if (higher != null && higher - num == k + 1 ) {
78+
return i + 1;
79+
}
80+
if (lower != null && num - lower == k + 1) {
81+
return i + 1;
82+
}
83+
}
84+
85+
return -1;
86+
}
87+
}
88+
89+
90+
// Track days of slot of days
91+
class Solution {
92+
public int kEmptySlots(int[] flowers, int k) {
93+
if (flowers == null || flowers.length == 0 || k < 0) {
94+
return - 1;
95+
}
96+
int n = flowers.length;
97+
int[] days = new int[n];
98+
for (int i = 0; i < n; i++) {
99+
days[flowers[i] - 1] = i + 1; // 1-based
100+
}
101+
102+
int left = 0, right = k + 1, result = Integer.MAX_VALUE;
103+
for (int i = 0; right < n; i++) {
104+
if (days[i] < days[left] || days[i] <= days[right]) {
105+
if (i == right) {
106+
result = Math.min(result, Math.max(days[left], days[right]));
107+
}
108+
left = i;
109+
right = k + 1 + i;
110+
}
111+
}
112+
return result == Integer.MAX_VALUE ? - 1 : result;
113+
}
114+
}
115+
116+
```

‎Java/LFU Cache.java‎

Lines changed: 76 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,76 @@
1+
H
2+
tags: Design, Hash Table
3+
4+
#### Hash Table
5+
- 具体看thoughts, 几种不同的方式使用map
6+
- `regular object map`: map of <key, item>, where `item : {int val; int count}`
7+
- `frequency list map`: map of <frequency count, List<item>>, where the list preserves `recency`
8+
- `item location in frequency map`: map of <key, int location index in list>:
9+
- index relative to the item in a particular list, not tracking which list here
10+
- Track constant capacity, and minimum frequency
11+
- Every get(): update all 3 data structures
12+
- Every put(): update all 3 data structures, with optional removal (if over capacity)
13+
- TODO: code it up
14+
15+
```
16+
/*
17+
Design and implement a data structure for Least Frequently Used (LFU) cache.
18+
It should support the following operations: get and put.
19+
20+
get(key) - Get the value (will always be positive) of the key
21+
if the key exists in the cache, otherwise return -1.
22+
23+
put(key, value) - Set or insert the value if the key is not already present.
24+
When the cache reaches its capacity, it should invalidate the least frequently used item
25+
before inserting a new item. For the purpose of this problem,
26+
when there is a tie (i.e., two or more keys that have the same frequency),
27+
the least recently used key would be evicted.
28+
29+
Follow up:
30+
Could you do both operations in O(1) time complexity?
31+
32+
Example:
33+
34+
LFUCache cache = new LFUCache( 2 ); // capacity
35+
36+
cache.put(1, 1);
37+
cache.put(2, 2);
38+
cache.get(1); // returns 1
39+
cache.put(3, 3); // evicts key 2
40+
cache.get(2); // returns -1 (not found)
41+
cache.get(3); // returns 3.
42+
cache.put(4, 4); // evicts key 1.
43+
cache.get(1); // returns -1 (not found)
44+
cache.get(3); // returns 3
45+
cache.get(4); // returns 4
46+
47+
*/
48+
49+
50+
/*
51+
Goal:
52+
get(key): value(+ int), -1
53+
put(key, val).
54+
if at cap, remove least frequent (smallest count); if count equal, remove old key
55+
option1. pq, to store sort the order (frequency, recency). O(logn) for insertion. NOT OKAY
56+
option2:
57+
- hashmap to find value by key quickly,
58+
- frequency map to track <frequency #, list of items>
59+
- freqPosition map to track <key, item position in frequency list>
60+
- int minFrequency to track the lowest frequency (to remove when reached capacity)
61+
- constant capacity
62+
63+
Option2 gives O(1) get(); put() avg O(1)
64+
65+
Get:
66+
Find key from map, retrieve existing frequency and find it on freqMap, move the item to a new frequency++ on freqMap, update freqPosition
67+
68+
Put:
69+
If exist, simply update the value for the key, return.
70+
If not exist:
71+
- (optional)if over capacity: find freqMap[minFreq]'s least frequent item, remove item.key from map, remove item.key freqPosition map, remove the item from freqMap (first item in the list)
72+
- it's new item with freq==1, add to hashmap, add to frequency map, and add the freq list position to freqPosition.
73+
74+
*/
75+
76+
```

‎Java/Maximum Average Subarray II.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
R
22
1521096472
3-
tags: Array, Binary Search
3+
tags: Array, Binary Search, PreSum
44

55
给int[] nums 和 window min size k. window size可以大于K. 找最大的连续数列average value.
66

‎Java/Maximum Subarray II.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
M
22
1525363049
3-
tags: Greedy, Array, DP, Sequence DP
3+
tags: Greedy, Array, DP, Sequence DP, PreSum
44

55
给一串数组, 找数组中间 两个不交互的 subarray 数字之和的最大值
66

‎Java/Maximum Subarray.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
E
22
1525331164
3-
tags: DP, Sequence DP, Array, Divide and Conquer, DFS
3+
tags: DP, Sequence DP, Array, Divide and Conquer, DFS, PreSum
44

55
给一串数组, 找数组中间 subarray 数字之和的最大值
66

‎KnowledgeHash.md‎

Lines changed: 4 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -357,8 +357,10 @@ stack.push(item);
357357

358358
## TreeSet
359359
- 如果BST treenode没给, 可以用TreeSet
360-
- TreeSet还是一个set, 存values, 而好处是可以用 treeSet.ceiling(x)找到 最小的大于x的值
361-
- 其实就是这个value/node的parent
360+
- TreeSet还是一个set, 存values, 而好处是可以用 `treeSet.ceiling(x)` 找到 最小 >= x的值
361+
- 同样, 找 <= x, 用 `treeSet.floor(x)`
362+
- strict less or greater: `treeSet.lower(x)`, `treeSet.higher(x)`
363+
- time O(nlogn)
362364

363365
## Traversal
364366
- Inorder BST traversal: 从小到大排序的ouput

0 commit comments

Comments
 (0)