Skip to content

Commit c257656

Browse files
awangdevawangdev
committed
hash table
1 parent 9094d0a commit c257656

16 files changed

Lines changed: 707 additions & 169 deletions

‎Java/Contiguous Array.java‎

Lines changed: 76 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,76 @@
1+
M
2+
1531902072
3+
tags: Hash Table
4+
5+
TODO: how aout without chaning the input nums?
6+
7+
```
8+
/*
9+
Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.
10+
11+
Example 1:
12+
Input: [0,1]
13+
Output: 2
14+
Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.
15+
16+
Example 2:
17+
Input: [0,1,0]
18+
Output: 2
19+
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.
20+
Note: The length of the given binary array will not exceed 50,000.
21+
*/
22+
/*
23+
k = sum - i - 1
24+
check if map.containsKey(preSum - k). If so, Math.max(max, i - map.get(preSum - k))
25+
*/
26+
27+
28+
class Solution {
29+
public int findMaxLength(int[] nums) {
30+
if (nums == null || nums.length == 0) return 0;
31+
for (int i = 0; i < nums.length; i++) {
32+
if (nums[i] == 0) nums[i] = -1;
33+
}
34+
Map<Integer, Integer> map = new HashMap<>();
35+
map.put(0, -1);
36+
37+
int preSum = 0, max = 0;
38+
for (int i = 0; i < nums.length; i++) {
39+
preSum += nums[i];
40+
if (map.containsKey(preSum)) {
41+
max = Math.max(max, i - map.get(preSum));
42+
}
43+
if (!map.containsKey(preSum)) {
44+
map.put(preSum, i);
45+
}
46+
}
47+
48+
return max;
49+
}
50+
}
51+
52+
// TODO: what if not reseting 0 -> -1, can we solve this?
53+
// Also, inspired by Buy/Sell Stock https://leetcode.com/problems/contiguous-array/discuss/99655/Python-O(n)-Solution-with-Visual-Explanation
54+
class Solution {
55+
public int findMaxLength(int[] nums) {
56+
if (nums == null || nums.length == 0) return 0;
57+
Map<Integer, Integer> map = new HashMap<>();
58+
map.put(0, -1);
59+
60+
int preSum = 0, max = 0;
61+
for (int i = 0; i < nums.length; i++) {
62+
preSum += nums[i];
63+
int k = preSum - i - 1;
64+
if (map.containsKey(preSum - k)) {
65+
max = Math.max(max, i - map.get(preSum - k));
66+
}
67+
if (!map.containsKey(preSum)) {
68+
map.put(preSum, i);
69+
}
70+
}
71+
72+
return max;
73+
}
74+
}
75+
76+
```

‎Java/Kth Largest Element in an Array.java‎

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
M
2+
1531896299
3+
tags: Divide and Conquer, Heap
4+
5+
```
6+
/**
7+
Find the kth largest element in an unsorted array.
8+
Note that it is the kth largest element in the sorted order, not the kth distinct element.
9+
10+
Example 1:
11+
12+
Input: [3,2,1,5,6,4] and k = 2
13+
Output: 5
14+
Example 2:
15+
16+
Input: [3,2,3,1,2,4,5,5,6] and k = 4
17+
Output: 4
18+
Note:
19+
You may assume k is always valid, 1 ≤ k ≤ array's length.
20+
*/
21+
22+
/*
23+
sort O(nlogn). Better O(n)
24+
use a min-heap with size k, so min item will always be at top to be removed O(logk)
25+
Overall runtime O(nlogk)
26+
*/
27+
class Solution {
28+
public int findKthLargest(int[] nums, int k) {
29+
if (nums == null || nums.length == 0) return -1;
30+
31+
PriorityQueue<Integer> queue = new PriorityQueue<>(); // min-heap
32+
33+
for (int i = 0; i < nums.length; i++) {
34+
if (i < k || nums[i] > queue.peek()) queue.offer(nums[i]);
35+
if (queue.size() > k) queue.poll();
36+
}
37+
38+
return queue.poll();
39+
}
40+
}
41+
```

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

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
M
2+
1531896141
3+
tags: Hash Table, PreSum
4+
time: O(n)
5+
space: O(n)
6+
7+
#### Map<preSumValue, index>
8+
- use `Map<preSum value, index>` to store inline preSum and its index.
9+
- 1. Build presum incline
10+
- 2. Use map to cache current preSum value and its index: `Map<preSum value, index>`
11+
- 3. Each iteration: calculate possible preSum candidate that prior target sequence. ex: `(preSum - k)`
12+
- 4. Use the calculated preSum candidate to find index
13+
- 5. Use found index to calculate for result. ex: calculate range.
14+
15+
```
16+
/*
17+
Given an array nums and a target value k, find the maximum length of a subarray that sums to k.
18+
If there isn't one, return 0 instead.
19+
20+
Note:
21+
The sum of the entire nums array is guaranteed to fit within the 32-bit signed integer range.
22+
23+
Example 1:
24+
25+
Input: nums = [1, -1, 5, -2, 3], k = 3
26+
Output: 4
27+
Explanation: The subarray [1, -1, 5, -2] sums to 3 and is the longest.
28+
Example 2:
29+
30+
Input: nums = [-2, -1, 2, 1], k = 1
31+
Output: 2
32+
Explanation: The subarray [-1, 2] sums to 1 and is the longest.
33+
Follow Up:
34+
Can you do it in O(n) time?
35+
36+
*/
37+
38+
/*
39+
Same concept as 2 sum
40+
1. calcualte preSum as we go
41+
2. store presum and the index in map<preSum, index>
42+
3. if @ any index: map.containsKey(presum - k), then the starting index was available: [startIndex, i]
43+
4. maintain global variable
44+
*/
45+
class Solution {
46+
public int maxSubArrayLen(int[] nums, int k) {
47+
if (nums == null || nums.length == 0) return 0;
48+
Map<Integer, Integer> map = new HashMap<>();
49+
map.put(0, -1);
50+
int preSum = 0, max = 0;
51+
for (int i = 0; i < nums.length; i++) {
52+
preSum += nums[i];
53+
if (map.containsKey(preSum - k)) {
54+
max = Math.max(max, i - map.get(preSum - k));
55+
}
56+
if (!map.containsKey(preSum)) {
57+
map.put(preSum, i);
58+
}
59+
}
60+
return max;
61+
}
62+
}
63+
```

‎Java/Target Sum.java‎

Lines changed: 71 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,71 @@
1+
M
2+
1531896045
3+
tags: DP, DFS
4+
5+
// 如何想到从中间initialize
6+
7+
```
8+
/*
9+
You are given a list of non-negative integers, a1, a2, ..., an, and a target, S.
10+
Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.
11+
12+
Find out how many ways to assign symbols to make sum of integers equal to target S.
13+
14+
Example 1:
15+
Input: nums is [1, 1, 1, 1, 1], S is 3.
16+
Output: 5
17+
Explanation:
18+
19+
-1+1+1+1+1 = 3
20+
+1-1+1+1+1 = 3
21+
+1+1-1+1+1 = 3
22+
+1+1+1-1+1 = 3
23+
+1+1+1+1-1 = 3
24+
25+
There are 5 ways to assign symbols to make the sum of nums be target 3.
26+
Note:
27+
The length of the given array is positive and will not exceed 20.
28+
The sum of elements in the given array will not exceed 1000.
29+
Your output answer is guaranteed to be fitted in a 32-bit integer.
30+
*/
31+
32+
/*
33+
target S range [-1000, 1000]
34+
dp[i][amount]: for the first i items, # of ways to sum up to certain amount
35+
dp[i][j] = dp[i-1][j - nums[i-1]] + dp[i-1][j + nums[i-1]]; negative, or positive on item[i-1]. 加法原理.
36+
int[][] dp = new int[n+1][S+1]
37+
dp[0][anyamount] = 0;
38+
dp[1][num[0]] = 1;
39+
40+
// set up Math.abs(S); if negative, the # of ways will be the same for the absolute value.
41+
goal: dp[n][S]
42+
*/
43+
class Solution {
44+
public int findTargetSumWays(int[] nums, int S) {
45+
if (nums == null || nums.length == 0) return 0;
46+
47+
int sum = 0;
48+
for (int num : nums) sum += num;
49+
if (sum < Math.abs(S)) return 0;
50+
51+
// create dp, and init
52+
int n = nums.length, m = (sum << 1) + 1;
53+
int[][] dp = new int[n][m];
54+
dp[0][sum - nums[0]] += 1;
55+
dp[0][sum + nums[0]] += 1;
56+
57+
for (int i = 1; i < n; i++) {
58+
for (int j = 0; j < m; j++) {
59+
if (j - nums[i] >= 0) {
60+
dp[i][j] += dp[i - 1][j - nums[i]];
61+
}
62+
if (j + nums[i] < m) {
63+
dp[i][j] += dp[i - 1][j + nums[i]];
64+
}
65+
}
66+
}
67+
68+
return dp[n - 1][S + sum];
69+
}
70+
}
71+
```

‎LevelReviewPage.md‎

Lines changed: 43 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2245,7 +2245,7 @@ space: O(1) greedy, O(n) dp
22452245

22462246

22472247

2248-
## Medium (224)
2248+
## Medium (228)
22492249
**0. [Delete Digits.java](https://github.com/awangdev/LintCode/blob/master/Java/Delete%20Digits.java)** Level: Medium Tags: []
22502250

22512251

@@ -6816,6 +6816,48 @@ space: O(X), X = max wall width
68166816

68176817
---
68186818

6819+
**224. [Target Sum.java](https://github.com/awangdev/LintCode/blob/master/Java/Target%20Sum.java)** Level: Medium Tags: [DFS, DP]
6820+
6821+
6822+
// 如何想到从中间initialize
6823+
6824+
6825+
6826+
---
6827+
6828+
**225. [Maximum Size Subarray Sum Equals k.java](https://github.com/awangdev/LintCode/blob/master/Java/Maximum%20Size%20Subarray%20Sum%20Equals%20k.java)** Level: Medium Tags: [Hash Table, PreSum]
6829+
6830+
time: O(n)
6831+
space: O(n)
6832+
6833+
#### Map<preSumValue, index>
6834+
- use `Map<preSum value, index>` to store inline preSum and its index.
6835+
- 1. Build presum incline
6836+
- 2. Use map to cache current preSum value and its index: `Map<preSum value, index>`
6837+
- 3. Each iteration: calculate possible preSum candidate that prior target sequence. ex: `(preSum - k)`
6838+
- 4. Use the calculated preSum candidate to find index
6839+
- 5. Use found index to calculate for result. ex: calculate range.
6840+
6841+
6842+
6843+
---
6844+
6845+
**226. [Kth Largest Element in an Array.java](https://github.com/awangdev/LintCode/blob/master/Java/Kth%20Largest%20Element%20in%20an%20Array.java)** Level: Medium Tags: [Divide and Conquer, Heap]
6846+
6847+
6848+
6849+
6850+
---
6851+
6852+
**227. [Contiguous Array.java](https://github.com/awangdev/LintCode/blob/master/Java/Contiguous%20Array.java)** Level: Medium Tags: [Hash Table]
6853+
6854+
6855+
TODO: how aout without chaning the input nums?
6856+
6857+
6858+
6859+
---
6860+
68196861

68206862

68216863

‎README.md‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -471,3 +471,7 @@
471471
|450|[Accounts Merge.java](https://github.com/awangdev/LintCode/blob/master/Java/Accounts%20Merge.java)|Medium|Java|[DFS, Hash Table, Union Find]||
472472
|451|[Exclusive Time of Functions.java](https://github.com/awangdev/LintCode/blob/master/Java/Exclusive%20Time%20of%20Functions.java)|Medium|Java|[Stack]||
473473
|452|[Friends Of Appropriate Ages.java](https://github.com/awangdev/LintCode/blob/master/Java/Friends%20Of%20Appropriate%20Ages.java)|Medium|Java|[Array, Math]||
474+
|453|[Target Sum.java](https://github.com/awangdev/LintCode/blob/master/Java/Target%20Sum.java)|Medium|Java|[DFS, DP]||
475+
|454|[Maximum Size Subarray Sum Equals k.java](https://github.com/awangdev/LintCode/blob/master/Java/Maximum%20Size%20Subarray%20Sum%20Equals%20k.java)|Medium|Java|[Hash Table, PreSum]||
476+
|455|[Kth Largest Element in an Array.java](https://github.com/awangdev/LintCode/blob/master/Java/Kth%20Largest%20Element%20in%20an%20Array.java)|Medium|Java|[Divide and Conquer, Heap]||
477+
|456|[Contiguous Array.java](https://github.com/awangdev/LintCode/blob/master/Java/Contiguous%20Array.java)|Medium|Java|[Hash Table]||

‎ReviewPage.md‎

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -8776,5 +8776,47 @@ space: O(X), X = max wall width
87768776

87778777

87788778

8779+
---
8780+
8781+
**453. [Target Sum.java](https://github.com/awangdev/LintCode/blob/master/Java/Target%20Sum.java)** Level: Medium Tags: [DFS, DP]
8782+
8783+
8784+
// 如何想到从中间initialize
8785+
8786+
8787+
8788+
---
8789+
8790+
**454. [Maximum Size Subarray Sum Equals k.java](https://github.com/awangdev/LintCode/blob/master/Java/Maximum%20Size%20Subarray%20Sum%20Equals%20k.java)** Level: Medium Tags: [Hash Table, PreSum]
8791+
8792+
time: O(n)
8793+
space: O(n)
8794+
8795+
#### Map<preSumValue, index>
8796+
- use `Map<preSum value, index>` to store inline preSum and its index.
8797+
- 1. Build presum incline
8798+
- 2. Use map to cache current preSum value and its index: `Map<preSum value, index>`
8799+
- 3. Each iteration: calculate possible preSum candidate that prior target sequence. ex: `(preSum - k)`
8800+
- 4. Use the calculated preSum candidate to find index
8801+
- 5. Use found index to calculate for result. ex: calculate range.
8802+
8803+
8804+
8805+
---
8806+
8807+
**455. [Kth Largest Element in an Array.java](https://github.com/awangdev/LintCode/blob/master/Java/Kth%20Largest%20Element%20in%20an%20Array.java)** Level: Medium Tags: [Divide and Conquer, Heap]
8808+
8809+
8810+
8811+
8812+
---
8813+
8814+
**456. [Contiguous Array.java](https://github.com/awangdev/LintCode/blob/master/Java/Contiguous%20Array.java)** Level: Medium Tags: [Hash Table]
8815+
8816+
8817+
TODO: how aout without chaning the input nums?
8818+
8819+
8820+
87798821
---
87808822

0 commit comments

Comments
 (0)