Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit26ffd0a

Browse files
committed
[Function add]
1. Add leetcode solutions.
1 parent231521b commit26ffd0a

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+
classMyHashMap {
34+
privateint[] map;
35+
/** Initialize your data structure here.*/
36+
publicMyHashMap() {
37+
this.map=newint[1000000];
38+
Arrays.fill(map,-1);
39+
}
40+
41+
/** value will always be non-negative.*/
42+
publicvoidput(intkey,intvalue) {
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+
publicintget(intkey) {
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+
publicvoidremove(intkey) {
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+
*Method2:Hash bucket+ collision handle+ adjacent table
67+
```Java
68+
classMyHashMap {
69+
privatestaticclassNode{
70+
int key;
71+
int val;
72+
Node next;
73+
publicNode(intkey,intval){
74+
this.key= key;
75+
this.val= val;
76+
}
77+
}
78+
privateNode[] bucket;
79+
privatestaticfinalint size=10000;
80+
/** Initialize your data structure here.*/
81+
publicMyHashMap() {
82+
this.bucket=newNode[size];
83+
}
84+
85+
/** value will always be non-negative.*/
86+
publicvoidput(intkey,intvalue) {
87+
int index= hash(key);
88+
if(bucket[index]==null) bucket[index]=newNode(-1,0);
89+
Node pre= find(bucket[index], key);
90+
if(pre.next==null) pre.next=newNode(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+
publicintget(intkey) {
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+
publicvoidremove(intkey) {
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+
privateNodefind(Nodehead,intkey){
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+
privateinthash(intkey){
119+
returnInteger.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+
classSolution {
125+
privateint[] heights;
126+
publicint[]pourWater(int[]heights,intV,intK) {
127+
this.heights= heights;
128+
while(V>0){
129+
drop(K);
130+
V--;
131+
}
132+
returnthis.heights;
133+
}
134+
privatevoiddrop(intk){
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+
}elseif(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+
}elseif(heights[pos]> cur)break;
150+
pos++;
151+
}
152+
this.heights[k]++;
153+
}
154+
}
155+
```
156+
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+
classSolution {
40+
publicintthreeSumMulti(int[]A,inttarget) {
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+
}elseif(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+
*Method2: O(n^2+ n)
71+
```Java
72+
classSolution {
73+
publicintthreeSumMulti(int[]A,inttarget) {
74+
int len=A.length;
75+
long res=0L;
76+
long[] map=newlong[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+
elseif(i== j) res+= map[c]* map[i]* (map[i]-1)/2;
86+
elseif(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. [花花酱LeetCode923. 3SumWithMultiplicity](https://zxi.mytechroad.com/blog/hashtable/leetcode-923-3sum-with-multiplicity/)

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp