找出二維數(shù)組中連成1組成的部分的數(shù)量凯正。
- 時(shí)間復(fù)雜度 O(MN)
- 空間復(fù)雜度O(MN)
dfs，對(duì)二維網(wǎng)格進(jìn)行遍歷，對(duì)其上下左右節(jié)點(diǎn)進(jìn)行遞歸感帅，將已經(jīng)識(shí)別過的1處理成0，dfs最重要的是要找到退出條件地淀，越過矩陣邊界或元素本身為0
- Runtime: 80 ms, faster than 93.00%
- Memory Usage: 39.9 MB, less than 54.87%
/**
* @param {character[][]} grid
* @return {number}
*/
var numIslands = function(grid) {
let m = grid.length
let n = grid[0].length
let res = 0
if (m === 0 || n === 0) return res
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if(grid[i][j] === '1') {
res++
dfs(i, j, grid)
}
}
}
return res
};
var dfs = function(i, j, grid) {
if(grid[i][j] === '0') return
let m = grid.length
let n = grid[0].length
grid[i][j] = '0'
if (i - 1 >= 0 && grid[i - 1][j]) dfs(i - 1, j, grid)
if (i + 1 < m && grid[i + 1][j]) dfs(i + 1, j, grid)
if (j - 1 >= 0 && grid[i][j - 1]) dfs(i, j - 1, grid)
if (j + 1 < n && grid[i][j + 1]) dfs(i, j + 1, grid)
}
