Pour Water
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public int[] pourWater(int[] heights, int V, int K) {
while (V > 0) {
int i = K;
while (i > 0 && heights[i] >= heights[i - 1]) {
i--;
}
while (i < heights.length - 1 && heights[i] >= heights[i + 1]) {
i++;
}
while (i > K && heights[i] == heights[i - 1]) {
i--;
}
heights[i]++;
V--;
}
return heights;
}
|
Champagne Tower
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public double champagneTower(int poured, int query_row, int query_glass) {
double[][] glass = new double[query_row + 2][query_row + 2];
glass[0][0] = poured;
for (int i = 0; i <= query_row; i++) {
for (int j = 0; j <= i; j++) {
if (glass[i][j] > 1) {
double water = (glass[i][j] - 1) / 2;
glass[i + 1][j] += water;
glass[i + 1][j + 1] += water;
}
}
}
return Math.min(glass[query_row][query_glass], 1);
}
|
Reduced to 1D:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public double champagneTower(int poured, int query_row, int query_glass) {
double[] glass = new double[query_row + 2];
glass[0] = poured;
for (int i = 1; i <= query_row; i++) {
for (int j = i; j >= 0; j--) {
double water = Math.max((glass[j] - 1) / 2, 0);
glass[j] = water;
glass[j + 1] += water;
}
}
return Math.min(glass[query_glass], 1);
}
|
Dota2 Senate
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public String predictPartyVictory(String senate) {
Queue<Integer> r = new LinkedList<>(), d = new LinkedList<>();
int n = senate.length();
for (int i = 0; i< n; i++) {
if (senate.charAt(i) == 'R') {
r.offer(i);
} else {
d.offer(i);
}
}
while (!r.isEmpty() && !d.isEmpty()) {
int ri = r.poll(), di = d.poll();
if (ri < di) {
r.offer(ri + n);
} else {
d.offer(di + n);
}
}
return r.size() > d.size() ? "Radiant" : "Dire";
}
|
Where Will the Ball Fall
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public int[] findBall(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[] answer = new int[n];
for (int j = 0; j < n; j++) {
int j1 = j, j2 = 0;
for (int i = 0; i < m; i++) {
// next possible column
j2 = j1 + grid[i][j1];
// if a ball can move from j1 to j2
// grid[i][j1] == grid[i][j2]
if (j2 < 0 || j2 >= n || grid[i][j2] != grid[i][j1]) {
j1 = -1;
break;
}
// prepares for next row
j1 = j2;
}
answer[j] = j1;
}
return answer;
}
|
Number of Spaces Cleaning Robot Cleaned
When the robot reaches a space that it has already cleaned and is facing the same direction as before, we can stop the simulation.
Reveal Cards In Increasing Order
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public int[] deckRevealedIncreasing(int[] deck) {
Arrays.sort(deck);
int n = deck.length;
int[] order = new int[n];
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < n; i++) {
q.offer(i);
}
int i = 0;
while (i < n) {
order[q.poll()] = deck[i++];
q.offer(q.poll());
}
return order;
}
|
Find Latest Group of Size M
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public int findLatestStep(int[] arr, int m) {
int n = arr.length;
if (n == m) {
return n;
}
int[] length = new int[n + 2];
int step = -1;
for (int i = 0; i < n; i++) {
int index = arr[i];
int left = length[index - 1], right = length[index + 1];
if (left == m || right == m) {
step = i;
}
length[index + right] = length[index - left] = length[index] = left + right + 1;
}
return step;
}
|