feat: add typescript solution to lc problem: No.0200.Number of Islands (doocs#470)

zhaocchen · web-flow · commit 89b35caf002a · 2021-06-22T15:04:52.000+08:00
diff --git a/solution/0200-0299/0200.Number of Islands/README.md b/solution/0200-0299/0200.Number of Islands/README.md
@@ -54,6 +54,8 @@
 
 <!-- 这里可写通用的实现逻辑 -->
 
+BFS/DFS 均可
+
 <!-- tabs:start -->
 
 ### **Python3**
@@ -72,6 +74,40 @@
 
 ```
 
+### **TypeScript**
+
+```ts
+function numIslands(grid: string[][]): number {
+    let m = grid.length, n = grid[0].length;
+    let ans = 0;
+    for (let i = 0; i < m; ++i) {
+        for (let j = 0; j < n; ++j) {
+            if (grid[i][j] == '1') {
+                bfs(grid, i, j)
+                ++ans;
+            }
+        }
+    }
+    return ans;
+};
+
+function bfs(grid: string[][], r: number, c: number): void {
+    let m = grid.length, n = grid[0].length;
+    let queue = new Array();
+    queue.push([r, c]);
+    while (queue.length > 0) {
+        let [i, j] = queue.shift();
+        for (let [dx, dy] of [[0, 1], [0, -1], [1, 0], [-1, 0]]) {
+            let x = i + dx, y = j + dy;
+            if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1') {
+                grid[x][y] = '0';
+                queue.push([x, y]);
+            }
+        }
+    }
+}
+```
+
 ### **...**
 
 ```
diff --git a/solution/0200-0299/0200.Number of Islands/README_EN.md b/solution/0200-0299/0200.Number of Islands/README_EN.md
@@ -60,6 +60,40 @@
 
 ```
 
+### **TypeScript**
+
+```ts
+function numIslands(grid: string[][]): number {
+    let m = grid.length, n = grid[0].length;
+    let ans = 0;
+    for (let i = 0; i < m; ++i) {
+        for (let j = 0; j < n; ++j) {
+            if (grid[i][j] == '1') {
+                bfs(grid, i, j)
+                ++ans;
+            }
+        }
+    }
+    return ans;
+};
+
+function bfs(grid: string[][], r: number, c: number): void {
+    let m = grid.length, n = grid[0].length;
+    let queue = new Array();
+    queue.push([r, c]);
+    while (queue.length > 0) {
+        let [i, j] = queue.shift();
+        for (let [dx, dy] of [[0, 1], [0, -1], [1, 0], [-1, 0]]) {
+            let x = i + dx, y = j + dy;
+            if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1') {
+                grid[x][y] = '0';
+                queue.push([x, y]);
+            }
+        }
+    }
+}
+```
+
 ### **...**
 
 ```
diff --git a/solution/0200-0299/0200.Number of Islands/Solution.ts b/solution/0200-0299/0200.Number of Islands/Solution.ts
@@ -0,0 +1,29 @@
+function numIslands(grid: string[][]): number {
+    let m = grid.length, n = grid[0].length;
+    let ans = 0;
+    for (let i = 0; i < m; ++i) {
+        for (let j = 0; j < n; ++j) {
+            if (grid[i][j] == '1') {
+                bfs(grid, i, j)
+                ++ans;
+            }
+        }
+    }
+    return ans;
+};
+
+function bfs(grid: string[][], r: number, c: number): void {
+    let m = grid.length, n = grid[0].length;
+    let queue = new Array();
+    queue.push([r, c]);
+    while (queue.length > 0) {
+        let [i, j] = queue.shift();
+        for (let [dx, dy] of [[0, 1], [0, -1], [1, 0], [-1, 0]]) {
+            let x = i + dx, y = j + dy;
+            if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1') {
+                grid[x][y] = '0';
+                queue.push([x, y]);
+            }
+        }
+    }
+}
