Skip to content

Commit 26ffd0a

Browse files
SeanforfunSeanforfun
committed
[Function add]
1. Add leetcode solutions.
1 parent 231521b commit 26ffd0a

File tree

3 files changed

+382
-0
lines changed

3 files changed

+382
-0
lines changed

‎leetcode/706. Design HashMap.md

Lines changed: 130 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,130 @@
1+
## 706. Design HashMap
2+
3+
### Question
4+
Design a HashMap without using any built-in hash table libraries.
5+
6+
To be specific, your design should include these functions:
7+
* put(key, value) : Insert a (key, value) pair into the HashMap. If the value already exists in the HashMap, update the value.
8+
* get(key): Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
9+
* remove(key) : Remove the mapping for the value key if this map contains the mapping for the key.
10+
11+
```
12+
Example:
13+
14+
MyHashMap hashMap = new MyHashMap();
15+
hashMap.put(1, 1);
16+
hashMap.put(2, 2);
17+
hashMap.get(1); // returns 1
18+
hashMap.get(3); // returns -1 (not found)
19+
hashMap.put(2, 1); // update the existing value
20+
hashMap.get(2); // returns 1
21+
hashMap.remove(2); // remove the mapping for 2
22+
hashMap.get(2); // returns -1 (not found)
23+
```
24+
25+
Note:
26+
1. All keys and values will be in the range of [0, 1000000].
27+
2. The number of operations will be in the range of [1, 10000].
28+
3. Please do not use the built-in HashMap library.
29+
30+
### Solutions:
31+
* Method 1: Array
32+
```Java
33+
class MyHashMap {
34+
private int[] map;
35+
/** Initialize your data structure here. */
36+
public MyHashMap() {
37+
this.map = new int[1000000];
38+
Arrays.fill(map, -1);
39+
}
40+
41+
/** value will always be non-negative. */
42+
public void put(int key, int value) {
43+
map[key] = value;
44+
}
45+
46+
/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
47+
public int get(int key) {
48+
return map[key];
49+
}
50+
51+
/** Removes the mapping of the specified value key if this map contains a mapping for the key */
52+
public void remove(int key) {
53+
map[key] = -1;
54+
}
55+
}
56+
57+
/**
58+
* Your MyHashMap object will be instantiated and called as such:
59+
* MyHashMap obj = new MyHashMap();
60+
* obj.put(key,value);
61+
* int param_2 = obj.get(key);
62+
* obj.remove(key);
63+
*/
64+
```
65+
66+
* Method 2: Hash bucket + collision handle + adjacent table
67+
```Java
68+
class MyHashMap {
69+
private static class Node{
70+
int key;
71+
int val;
72+
Node next;
73+
public Node(int key, int val){
74+
this.key = key;
75+
this.val = val;
76+
}
77+
}
78+
private Node[] bucket;
79+
private static final int size = 10000;
80+
/** Initialize your data structure here. */
81+
public MyHashMap() {
82+
this.bucket = new Node[size];
83+
}
84+
85+
/** value will always be non-negative. */
86+
public void put(int key, int value) {
87+
int index = hash(key);
88+
if(bucket[index] == null) bucket[index] = new Node(-1, 0);
89+
Node pre = find(bucket[index], key);
90+
if(pre.next == null) pre.next = new Node(key, value);
91+
else pre.next.val = value;
92+
}
93+
94+
/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
95+
public int get(int key) {
96+
int index = hash(key);
97+
Node pre = find(bucket[index], key);
98+
if(pre == null || pre.next == null) return -1;
99+
return pre.next.val;
100+
}
101+
102+
/** Removes the mapping of the specified value key if this map contains a mapping for the key */
103+
public void remove(int key) {
104+
int index = hash(key);
105+
Node pre = find(bucket[index], key);
106+
if(pre == null || pre.next == null) return;
107+
pre.next = pre.next.next;
108+
}
109+
private Node find(Node head, int key){
110+
if(head == null) return head;
111+
Node pre = head, temp = head.next;
112+
while(temp != null && temp.key != key){
113+
pre = temp;
114+
temp = temp.next;
115+
}
116+
return pre;
117+
}
118+
private int hash(int key){
119+
return Integer.hashCode(key) % size;
120+
}
121+
}
122+
123+
/**
124+
* Your MyHashMap object will be instantiated and called as such:
125+
* MyHashMap obj = new MyHashMap();
126+
* obj.put(key,value);
127+
* int param_2 = obj.get(key);
128+
* obj.remove(key);
129+
*/
130+
```

‎leetcode/755. Pour Water.md

Lines changed: 156 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,156 @@
1+
## 755. Pour Water
2+
3+
### Question
4+
We are given an elevation map, heights[i] representing the height of the terrain at that index. The width at each index is 1. After V units of water fall at index K, how much water is at each index?
5+
6+
Water first drops at index K and rests on top of the highest terrain or water at that index. Then, it flows according to the following rules:
7+
* If the droplet would eventually fall by moving left, then move left.
8+
* Otherwise, if the droplet would eventually fall by moving right, then move right.
9+
* Otherwise, rise at it's current position.
10+
Here, "eventually fall" means that the droplet will eventually be at a lower level if it moves in that direction. Also, "level" means the height of the terrain plus any water in that column.
11+
12+
We can assume there's infinitely high terrain on the two sides out of bounds of the array. Also, there could not be partial water being spread out evenly on more than 1 grid block - each unit of water has to be in exactly one block.
13+
14+
```
15+
Example 1:
16+
17+
Input: heights = [2,1,1,2,1,2,2], V = 4, K = 3
18+
Output: [2,2,2,3,2,2,2]
19+
Explanation:
20+
# #
21+
# #
22+
## # ###
23+
#########
24+
0123456 <- index
25+
26+
The first drop of water lands at index K = 3:
27+
28+
# #
29+
# w #
30+
## # ###
31+
#########
32+
0123456
33+
34+
When moving left or right, the water can only move to the same level or a lower level.
35+
(By level, we mean the total height of the terrain plus any water in that column.)
36+
Since moving left will eventually make it fall, it moves left.
37+
(A droplet "made to fall" means go to a lower height than it was at previously.)
38+
39+
# #
40+
# #
41+
## w# ###
42+
#########
43+
0123456
44+
45+
Since moving left will not make it fall, it stays in place. The next droplet falls:
46+
47+
# #
48+
# w #
49+
## w# ###
50+
#########
51+
0123456
52+
53+
Since the new droplet moving left will eventually make it fall, it moves left.
54+
Notice that the droplet still preferred to move left,
55+
even though it could move right (and moving right makes it fall quicker.)
56+
57+
# #
58+
# w #
59+
## w# ###
60+
#########
61+
0123456
62+
63+
# #
64+
# #
65+
##ww# ###
66+
#########
67+
0123456
68+
69+
After those steps, the third droplet falls.
70+
Since moving left would not eventually make it fall, it tries to move right.
71+
Since moving right would eventually make it fall, it moves right.
72+
73+
# #
74+
# w #
75+
##ww# ###
76+
#########
77+
0123456
78+
79+
# #
80+
# #
81+
##ww#w###
82+
#########
83+
0123456
84+
85+
Finally, the fourth droplet falls.
86+
Since moving left would not eventually make it fall, it tries to move right.
87+
Since moving right would not eventually make it fall, it stays in place:
88+
89+
# #
90+
# w #
91+
##ww#w###
92+
#########
93+
0123456
94+
95+
The final answer is [2,2,2,3,2,2,2]:
96+
97+
#
98+
#######
99+
#######
100+
0123456
101+
102+
Example 2:
103+
104+
Input: heights = [1,2,3,4], V = 2, K = 2
105+
Output: [2,3,3,4]
106+
Explanation:
107+
The last droplet settles at index 1, since moving further left would not cause it to eventually fall to a lower height.
108+
109+
Example 3:
110+
111+
Input: heights = [3,1,3], V = 5, K = 1
112+
Output: [4,4,4]
113+
```
114+
115+
Note:
116+
1. heights will have length in [1, 100] and contain integers in [0, 99].
117+
2. V will be in range [0, 2000].
118+
3. K will be in range [0, heights.length - 1].
119+
120+
121+
### Solutions:
122+
* Method 1: Recursion 15min
123+
```Java
124+
class Solution {
125+
private int[] heights;
126+
public int[] pourWater(int[] heights, int V, int K) {
127+
this.heights = heights;
128+
while(V > 0){
129+
drop(K);
130+
V--;
131+
}
132+
return this.heights;
133+
}
134+
private void drop(int k){
135+
int pos = k - 1;
136+
int cur = heights[k];
137+
while(pos >= 0){
138+
if(heights[pos] < cur){
139+
drop(pos);
140+
return;
141+
}else if(heights[pos] > cur) break;
142+
pos--;
143+
}
144+
pos = k + 1;
145+
while(pos < heights.length){
146+
if(heights[pos] < heights[k]){
147+
drop(pos);
148+
return;
149+
}else if(heights[pos] > cur) break;
150+
pos++;
151+
}
152+
this.heights[k]++;
153+
}
154+
}
155+
```
156+

‎leetcode/923. 3Sum With Multiplicity.md

Lines changed: 96 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,96 @@
1+
## 923. 3Sum With Multiplicity
2+
3+
### Question
4+
Given an integer array A, and an integer target, return the number of tuples i, j, k such that i < j < k and A[i] + A[j] + A[k] == target.
5+
6+
As the answer can be very large, return it modulo 10^9 + 7.
7+
8+
```
9+
Example 1:
10+
11+
Input: A = [1,1,2,2,3,3,4,4,5,5], target = 8
12+
Output: 20
13+
Explanation:
14+
Enumerating by the values (A[i], A[j], A[k]):
15+
(1, 2, 5) occurs 8 times;
16+
(1, 3, 4) occurs 8 times;
17+
(2, 2, 4) occurs 2 times;
18+
(2, 3, 3) occurs 2 times.
19+
20+
Example 2:
21+
22+
Input: A = [1,1,2,2,2,2], target = 5
23+
Output: 12
24+
Explanation:
25+
A[i] = 1, A[j] = A[k] = 2 occurs 12 times:
26+
We choose one 1 from [1,1] in 2 ways,
27+
and two 2s from [2,2,2,2] in 6 ways.
28+
```
29+
30+
Note:
31+
1. 3 <= A.length <= 3000
32+
2. 0 <= A[i] <= 100
33+
3. 0 <= target <= 300
34+
35+
36+
### Solutions:
37+
* Method 1: TLE
38+
```Java
39+
class Solution {
40+
public int threeSumMulti(int[] A, int target) {
41+
int len = A.length;
42+
long res = 0;
43+
Arrays.sort(A); //O(nlgn)
44+
for(int i = 0; i < len - 2; i++){ //O(nlgn)
45+
int t = target - A[i];
46+
int slow = i + 1, fast = len - 1;
47+
while(slow < fast){
48+
int sum = A[slow] + A[fast];
49+
if(sum < t){
50+
slow++;
51+
}else if(sum > t){
52+
fast--;
53+
}else{
54+
//first move the fast pointer.
55+
int originalFast = fast;
56+
while(slow < fast && A[slow] + A[fast] == t){
57+
res++;
58+
fast--;
59+
}
60+
fast = originalFast;
61+
slow++;
62+
}
63+
}
64+
}
65+
return (int)(res % (1_000_000_007));
66+
}
67+
}
68+
```
69+
70+
* Method 2: O(n^2 + n)
71+
```Java
72+
class Solution {
73+
public int threeSumMulti(int[] A, int target) {
74+
int len = A.length;
75+
long res = 0L;
76+
long[] map = new long[101];
77+
for(int a : A){
78+
map[a]++;
79+
}
80+
for(int i = 0; i <= 100; i++){
81+
for(int j = i; j <= 100; j++){
82+
int c = target - i - j;
83+
if(c < j || c > 100 || map[i] == 0 || map[j] == 0 || map[c] == 0) continue;
84+
if(i == j && j == c) res += (map[i] * (map[i] - 1) * (map[i] - 2) / 6);
85+
else if(i == j) res += map[c] * map[i] * (map[i] - 1) / 2;
86+
else if(j == c) res += map[i] * map[j] * (map[j] - 1) / 2;
87+
else res += map[i] * map[j] * map[c];
88+
}
89+
}
90+
return (int)(res % (1_000_000_007));
91+
}
92+
}
93+
```
94+
95+
### Reference
96+
1. [花花酱 LeetCode 923. 3Sum With Multiplicity](https://zxi.mytechroad.com/blog/hashtable/leetcode-923-3sum-with-multiplicity/)

0 commit comments

Comments
 (0)