Skip to content

Commit 09f15b4

Browse files
fishercoder1534fishercoder1534
committed
add 755
1 parent 64bd659 commit 09f15b4

File tree

3 files changed

+243
-0
lines changed

3 files changed

+243
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -26,6 +26,7 @@ Your ideas/fixes/algorithms are more than welcome!
2626
|763|[Partition Labels](https://leetcode.com/problems/partition-labels/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_763.java) | O(n) | O(1) | |Medium|
2727
|762|[Prime Number of Set Bits in Binary Representation](https://leetcode.com/problems/prime-number-of-set-bits-in-binary-representation/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_762.java) | O(n) | O(1) | |Easy|
2828
|760|[Find Anagram Mappings](https://leetcode.com/problems/find-anagram-mappings/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_760.java) | O(n^2) | O(1) | |Easy|
29+
|755|[Pour Water](https://leetcode.com/problems/pour-water/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_755.java) | O(V*N) | O(1) | |Medium| Array
2930
|754|[Reach a Number](https://leetcode.com/problems/reach-a-number/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_754.java) | O(n) | O(1) | |Medium| Math
3031
|750|[Number Of Corner Rectangles](https://leetcode.com/problems/number-of-corner-rectangles/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_750.java) | O((m*n)^2) | O(1) | |Medium|
3132
|748|[Shortest Completing Word](https://leetcode.com/problems/shortest-completing-word/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_748.java) | O(n) | O(1) | |Easy|

‎src/main/java/com/fishercoder/solutions/_755.java

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

‎src/test/java/com/fishercoder/_755Test.java

Lines changed: 88 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,88 @@
1+
package com.fishercoder;
2+
3+
import com.fishercoder.solutions._755;
4+
import org.junit.BeforeClass;
5+
import org.junit.Test;
6+
7+
import static org.junit.Assert.assertArrayEquals;
8+
9+
public class _755Test {
10+
private static _755.Solution1 solution1;
11+
private static int[] heights;
12+
private static int[] expected;
13+
14+
@BeforeClass
15+
public static void setup() {
16+
solution1 = new _755.Solution1();
17+
}
18+
19+
@Test
20+
public void test1() {
21+
heights = new int[] {2, 1, 1, 2, 1, 2, 2};
22+
expected = new int[] {2, 2, 2, 3, 2, 2, 2};
23+
assertArrayEquals(expected, solution1.pourWater(heights, 4, 3));
24+
}
25+
26+
@Test
27+
public void test2() {
28+
heights = new int[] {1, 2, 3, 4};
29+
expected = new int[] {2, 3, 3, 4};
30+
assertArrayEquals(expected, solution1.pourWater(heights, 2, 2));
31+
}
32+
33+
@Test
34+
public void test3() {
35+
heights = new int[] {3, 1, 3};
36+
expected = new int[] {4, 4, 4};
37+
assertArrayEquals(expected, solution1.pourWater(heights, 5, 1));
38+
}
39+
40+
@Test
41+
public void test4() {
42+
heights = new int[] {1, 2, 3, 4, 3, 2, 1, 2, 3, 4, 3, 2, 1};
43+
expected = new int[] {1, 2, 3, 4, 3, 3, 2, 2, 3, 4, 3, 2, 1};
44+
assertArrayEquals(expected, solution1.pourWater(heights, 2, 5));
45+
}
46+
47+
@Test
48+
public void test5() {
49+
heights = new int[] {1, 2, 3, 4, 3, 2, 1, 2, 3, 4, 3, 2, 1};
50+
expected = new int[] {3, 4, 4, 4, 3, 2, 1, 2, 3, 4, 3, 2, 1};
51+
assertArrayEquals(expected, solution1.pourWater(heights, 5, 2));
52+
}
53+
54+
@Test
55+
public void test6() {
56+
heights = new int[] {1, 2, 3, 4, 3, 2, 1, 2, 3, 4, 3, 2, 1};
57+
expected = new int[] {4, 4, 4, 4, 3, 3, 3, 3, 3, 4, 3, 2, 1};
58+
assertArrayEquals(expected, solution1.pourWater(heights, 10, 2));
59+
}
60+
61+
@Test
62+
public void test7() {
63+
heights = new int[] {1, 2, 3, 4, 3, 2, 1, 2, 3, 4, 3, 2, 1};
64+
expected = new int[] {2, 3, 3, 4, 3, 2, 1, 2, 3, 4, 3, 2, 1};
65+
assertArrayEquals(expected, solution1.pourWater(heights, 2, 2));
66+
}
67+
68+
@Test
69+
public void test8() {
70+
heights = new int[] {1, 2, 3, 4, 3, 2, 1, 2, 3, 4, 3, 2, 1};
71+
expected = new int[] {3, 3, 3, 4, 3, 2, 1, 2, 3, 4, 3, 2, 1};
72+
assertArrayEquals(expected, solution1.pourWater(heights, 3, 2));
73+
}
74+
75+
@Test
76+
public void test9() {
77+
heights = new int[] {1, 2, 3, 4, 3, 2, 1, 2, 3, 4, 3, 2, 1};
78+
expected = new int[] {3, 3, 4, 4, 3, 2, 1, 2, 3, 4, 3, 2, 1};
79+
assertArrayEquals(expected, solution1.pourWater(heights, 4, 2));
80+
}
81+
82+
@Test
83+
public void test10() {
84+
heights = new int[] {1, 2, 3, 4, 3, 2, 1, 2, 3, 4, 3, 2, 1};
85+
expected = new int[] {3, 4, 4, 4, 3, 2, 1, 2, 3, 4, 3, 2, 1};
86+
assertArrayEquals(expected, solution1.pourWater(heights, 5, 2));
87+
}
88+
}

0 commit comments

Comments
 (0)