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

Commit b0861ba

Browse files
feat: add solutions to lc problem: No.0407 (#4762)
1 parent 6fed943 commit b0861ba

File tree

4 files changed

+118
-2
lines changed

4 files changed

+118
-2
lines changed

‎solution/0400-0499/0407.Trapping Rain Water II/README.md‎

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -208,6 +208,43 @@ func (h *hp) Push(v any) { *h = append(*h, v.(tuple)) }
208208
func (h *hp) Pop() any { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
209209
```
210210

211+
#### TypeScript
212+
213+
```ts
214+
function trapRainWater(heightMap: number[][]): number {
215+
const m = heightMap.length;
216+
const n = heightMap[0].length;
217+
const vis: boolean[][] = Array.from({ length: m }, () => new Array(n).fill(false));
218+
const pq = new MinPriorityQueue<[number, number, number]>({
219+
compare: (a, b) => a[0] - b[0],
220+
});
221+
for (let i = 0; i < m; ++i) {
222+
for (let j = 0; j < n; ++j) {
223+
if (i === 0 || i === m - 1 || j === 0 || j === n - 1) {
224+
pq.enqueue([heightMap[i][j], i, j]);
225+
vis[i][j] = true;
226+
}
227+
}
228+
}
229+
230+
let ans = 0;
231+
const dirs = [-1, 0, 1, 0, -1];
232+
while (!pq.isEmpty()) {
233+
const [h, i, j] = pq.dequeue();
234+
for (let k = 0; k < 4; ++k) {
235+
const x = i + dirs[k];
236+
const y = j + dirs[k + 1];
237+
if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y]) {
238+
ans += Math.max(0, h - heightMap[x][y]);
239+
vis[x][y] = true;
240+
pq.enqueue([Math.max(h, heightMap[x][y]), x, y]);
241+
}
242+
}
243+
}
244+
return ans;
245+
}
246+
```
247+
211248
<!-- tabs:end -->
212249

213250
<!-- solution:end -->

‎solution/0400-0499/0407.Trapping Rain Water II/README_EN.md‎

Lines changed: 42 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -55,7 +55,11 @@ The total volume of water trapped is 4.
5555

5656
<!-- solution:start -->
5757

58-
### Solution 1
58+
### Solution 1: Priority Queue (Min Heap)
59+
60+
This is a variant of the trapping rain water problem. Since the heights on the matrix boundaries are fixed, we can add these boundary heights to a priority queue. Then, we repeatedly take out the minimum height from the priority queue and compare it with the heights of its four adjacent cells. If an adjacent cell's height is less than the current height, we can trap water there. The volume of trapped water is the difference between the current height and the adjacent height. We then add the larger height back to the priority queue and repeat this process until the priority queue is empty.
61+
62+
The time complexity is $O(m \times n \times \log (m \times n)),ドル and the space complexity is $O(m \times n),ドル where $m$ and $n$ are the number of rows and columns in the matrix, respectively.
5963

6064
<!-- tabs:start -->
6165

@@ -198,6 +202,43 @@ func (h *hp) Push(v any) { *h = append(*h, v.(tuple)) }
198202
func (h *hp) Pop() any { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
199203
```
200204

205+
#### TypeScript
206+
207+
```ts
208+
function trapRainWater(heightMap: number[][]): number {
209+
const m = heightMap.length;
210+
const n = heightMap[0].length;
211+
const vis: boolean[][] = Array.from({ length: m }, () => new Array(n).fill(false));
212+
const pq = new MinPriorityQueue<[number, number, number]>({
213+
compare: (a, b) => a[0] - b[0],
214+
});
215+
for (let i = 0; i < m; ++i) {
216+
for (let j = 0; j < n; ++j) {
217+
if (i === 0 || i === m - 1 || j === 0 || j === n - 1) {
218+
pq.enqueue([heightMap[i][j], i, j]);
219+
vis[i][j] = true;
220+
}
221+
}
222+
}
223+
224+
let ans = 0;
225+
const dirs = [-1, 0, 1, 0, -1];
226+
while (!pq.isEmpty()) {
227+
const [h, i, j] = pq.dequeue();
228+
for (let k = 0; k < 4; ++k) {
229+
const x = i + dirs[k];
230+
const y = j + dirs[k + 1];
231+
if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y]) {
232+
ans += Math.max(0, h - heightMap[x][y]);
233+
vis[x][y] = true;
234+
pq.enqueue([Math.max(h, heightMap[x][y]), x, y]);
235+
}
236+
}
237+
}
238+
return ans;
239+
}
240+
```
241+
201242
<!-- tabs:end -->
202243

203244
<!-- solution:end -->
Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
function trapRainWater(heightMap: number[][]): number {
2+
const m = heightMap.length;
3+
const n = heightMap[0].length;
4+
const vis: boolean[][] = Array.from({ length: m }, () => new Array(n).fill(false));
5+
const pq = new MinPriorityQueue<[number, number, number]>({
6+
compare: (a, b) => a[0] - b[0],
7+
});
8+
for (let i = 0; i < m; ++i) {
9+
for (let j = 0; j < n; ++j) {
10+
if (i === 0 || i === m - 1 || j === 0 || j === n - 1) {
11+
pq.enqueue([heightMap[i][j], i, j]);
12+
vis[i][j] = true;
13+
}
14+
}
15+
}
16+
17+
let ans = 0;
18+
const dirs = [-1, 0, 1, 0, -1];
19+
while (!pq.isEmpty()) {
20+
const [h, i, j] = pq.dequeue();
21+
for (let k = 0; k < 4; ++k) {
22+
const x = i + dirs[k];
23+
const y = j + dirs[k + 1];
24+
if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y]) {
25+
ans += Math.max(0, h - heightMap[x][y]);
26+
vis[x][y] = true;
27+
pq.enqueue([Math.max(h, heightMap[x][y]), x, y]);
28+
}
29+
}
30+
}
31+
return ans;
32+
}

‎solution/3600-3699/3697.Compute Decimal Representation/README_EN.md‎

Lines changed: 7 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -72,7 +72,13 @@ edit_url: https://github.com/doocs/leetcode/edit/main/solution/3600-3699/3697.Co
7272

7373
<!-- solution:start -->
7474

75-
### Solution 1
75+
### Solution 1: Simulation
76+
77+
We can repeatedly perform modulo and division operations on $n$. Each modulo result multiplied by the current position value $p$ represents a decimal component. If the modulo result is not 0ドル,ドル we add this component to our answer. Then we multiply $p$ by 10ドル$ and continue processing the next position.
78+
79+
Finally, we reverse the answer to arrange it in descending order.
80+
81+
The time complexity is $O(\log n),ドル where $n$ is the input positive integer. The space complexity is $O(\log n)$ for storing the answer.
7682

7783
<!-- tabs:start -->
7884

0 commit comments

Comments
(0)

AltStyle によって変換されたページ (->オリジナル) /