Skip to content

Commit 0345377

Browse files
awangdevawangdev
committed
hashtable, subarray
1 parent 0c9a8e0 commit 0345377

43 files changed

Lines changed: 3784 additions & 2428 deletions

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

‎Java/Accounts Merge.java‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,10 @@
22
1531813218
33
tags: DFS, Union Find, Hash Table
44

5+
给一串account in format `[[name, email1, email2, email3], [name2, email,..]]`.
6+
7+
要求把所有account merge起来 (可能多个record记录了同一个人, by common email)
8+
59
#### Union Find
610
- TODO
711

‎Java/Continuous Subarray Sum.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
M
22
1522910259
3-
tags: Math, DP, Coordinate DP
3+
tags: Math, DP, Coordinate DP, Subarray
44

55
给一个非负数的数列和数字k(可正负, 可为0). 找到连续子序列(长度超过2), 使得这个subarray的sum 是 k的倍数. 问: 是否可能?
66

‎Java/Copy List with Random Pointer.java‎

Lines changed: 7 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,12 +1,16 @@
11
M
22
1527962398
33
tags: Hash Table, Linked List
4+
time: O(n)
5+
space: O(1)
46

57
deep copy linked list. linked list 上有random pointer to other nodes.
68

7-
#### HashMap
8-
- Basic Implementation
9+
#### HashMap, Linked List
10+
- Basic Implementation of copy linked list:
911
- use node and dummy to hold new list, 遍历head.next .... null.
12+
- Map 在这里用来: 1. avoid creating same node; 2. return the item if existing
13+
- map 的 key全部是old object, 新的key全部是 newly created object
1014
- 每一步都check map里面有没有head. 没有? 加上
1115
- 每一步都check map里面有没有head.random. 没有? 加上
1216

@@ -47,7 +51,7 @@ Hide Similar Problems (M) Clone Graph
4751
class Solution {
4852
public RandomListNode copyRandomList(RandomListNode head) {
4953
if (head == null) {
50-
return null;
54+
return head;
5155
}
5256
//creat node, used to link all nodes
5357
RandomListNode node = new RandomListNode(0);

‎Java/H-Index.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -23,7 +23,7 @@
2323
- bucket[x] 是 count when # of citation == x.
2424
- 如果 x 大于 n的时候, 就超出了index范围, 但是刚好这个问题可以包容, 把这样的情况记位在bucket[n]就可以
2525
- 巧妙: `sum += bucket[h]` where `h = [n ~ 0]` 利用了h-index的definition:
26-
- # of papers (sum of bucket[n]...bucket[0]) has more than h cidations
26+
- #of papers (sum of bucket[n]...bucket[0]) has more than h cidations
2727
- 这里运用到了bucket sort的思想, 但是并不是sorting, 而h-index的定义运用的很巧妙.
2828
- Read more about actual bucket sort: https://en.wikipedia.org/wiki/Bucket_sort
2929

‎Java/Maximum Average Subarray I.java‎

Lines changed: 5 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,11 @@
11
E
22
1517552169
3-
tags: Array
3+
tags: Array, Subarray
4+
time: O(n)
5+
space: O(1)
6+
7+
简单的求sum of fixed window k, 同时求max avg, 结尾求余数就好.
48

5-
简单的求sum, 同时求max, 结尾求余数就好.
69
```
710
/*
811
Given an array consisting of n integers, find the contiguous subarray of given length k

‎Java/Maximum Product Subarray.java‎

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

55
从一组数列(正负都有)里面找一串连续的子序列, 而达到乘积product最大值.
66

‎Java/Maximum Size Subarray Sum Equals k.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
M
22
1531896141
3-
tags: Hash Table, PreSum
3+
tags: Hash Table, PreSum, Subarray
44
time: O(n)
55
space: O(n)
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, PreSum
3+
tags: Greedy, Array, DP, Sequence DP, PreSum, Subarray
44

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

‎Java/Maximum Subarray.java‎

Lines changed: 17 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,10 @@
11
E
22
1525331164
3-
tags: DP, Sequence DP, Array, Divide and Conquer, DFS, PreSum
3+
tags: DP, Sequence DP, Array, Divide and Conquer, DFS, PreSum, Subarray
44
time: O(n)
55
space: O(n), O(1) rolling array
66

7-
给一串数组, 找数组中间 subarray 数字之和的最大值
7+
给一串数组, unsorted, can have negative/positive num. 找数组中间 subarray 数字之和的最大值
88

99
#### Sequence DP
1010
- dp[i]: 前i个element,包括 last element (i-1), 可能组成的 subarray 的最大sum.
@@ -58,6 +58,19 @@ If you have figured out the O(n) solution,
5858
5959
*/
6060

61+
// Despte the detailed dp[] solution, we have the light version:
62+
public class Solution {
63+
public int maxSubArray(int[] nums) {
64+
if (nums == null || nums.length == 0) return Integer.MIN_VALUE;
65+
int preMaxSum = 0, max = Integer.MIN_VALUE;
66+
for (int num : nums) {
67+
preMaxSum = Math.max(num, preMaxSum + num);
68+
max = Math.max(max, preMaxSum);
69+
}
70+
return max;
71+
}
72+
}
73+
6174
/*
6275
Thoughts:
6376
sequence dp
@@ -106,6 +119,8 @@ public int maxSubArray(int[] nums) {
106119
}
107120
}
108121

122+
123+
109124
// checking dp[i-1] >= 0. Same as Math.max(dp[i - 1] + nums[i - 1], nums[i - 1]);
110125
class Solution {
111126
public int maxSubArray(int[] nums) {

‎Java/Minimum Size Subarray Sum.java‎

Lines changed: 15 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -1,23 +1,24 @@
11
M
22
1519835840
3-
tags: Array, Two Pointers, Binary Search
3+
tags: Array, Two Pointers, Binary Search, Subarray
4+
time: O(n)
5+
space: O(1)
46

5-
方法1:
6-
2 pointer, O(n). 找subarray, start 或 end pointer，每次一格这样移动.
7+
给一串positive integer, 找最短的subarray sum, where the sum >= s
78

8-
好的策略:
9-
1. 先找一个solution, 定住end.
10-
2. 然后移动start; 记录每个solution if occurs
11-
3. 然后再移动end，往下找。
9+
#### Two pointer
10+
- 全部是positive integer, 那么preSum一定是增长的.
11+
- 那其实就用two pointer: `start=0, end=0` 不断往前移动. 策略:
12+
- 1. end++ until a solution where sum >= s is reached
13+
- 2. 然后移动start; 记录每个solution, Math.min(min, end - start);
14+
- 3. 然后再移动end，往下找
15+
- Note: 虽然一眼看上去是nested loop.但是分析后，发现其实就是按照end pointer移动的Loop。start每次移动一格。总体上，还是O(n)
1216

13-
Note: 虽然一眼看上去是nested loop.但是分析后，发现其实就是按照end pointer移动的Loop。start每次移动一格。总体上，还是O(n)
17+
#### Binary Search
18+
- O(nlogn) NOT DONE.
1419

15-
方法2:
16-
Double for loop, base i 每次只+1, 所以最后O(n^2)
17-
18-
方法3:
19-
Binary Search, O(nLogN)
20-
Not done yet
20+
#### Double For loop
21+
- O(n^2), inefficient
2122

2223
```
2324
/*

0 commit comments

Comments
 (0)