[数据结构与算法][leetcode] 200.岛屿数量

代码

DFS

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
    let count = 0
    for(let i = 0; i < grid.length; i++) {
        for(let j = 0; j < grid[0].length; j++) {
            if(grid[i][j] === '1') {
                count++
                // 深度优先遍历
                dfs(i, j, grid)
            }
        }
    }
    return count
};

let dfs = (i, j, grid) => {
	// 当grid[i][j]处于边界之外、或者当前为海
    if(i >= grid.length || j >= grid[0].length || i < 0 || j < 0 || grid[i][j] === '0') {
        return
    }
    // 此时说明当前是“陆地”
    grid[i][j] = '0'
	// 深度优先
    dfs(i, j+1, grid)
    dfs(i+1, j, grid)
    dfs(i-1, j, grid)
    dfs(i, j-1, grid)
}

思路

一个岛屿有n个陆地，对这其中的一个陆地进行深度遍历，直至周围都为“0”。即海时，完成一个岛屿的查找。

时间空间复杂度

1. 时间复杂度：O(m*n)，m为行数、n为列数。
2. 空间复杂度：O(m*n)

BFS

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
    let count = 0
    for(let i = 0; i < grid.length; i++) {
        for(let j = 0; j < grid[0].length; j++) {
            if(grid[i][j] === '1') {
                count++
                // 广度优先
                bfs(i, j, grid)
            }
        }
    }
    return count
};

let bfs = (a, b, grid) => {
    const queue = [[a, b]]
    while(queue.length) {
        const [i, j] = queue.shift()

        if(grid[i][j] === '1') {
            grid[i][j] = '0'

            if(((j + 1) < grid[0].length) && (j + 1) >= 0) {
                queue.push([i, j+1])
            }
            
            if(((i + 1) < grid.length) && (i + 1) >= 0) {
                queue.push([i+1, j])
            }

            if(((j - 1) < grid.length) && (j - 1) >= 0) {
                queue.push([i, j-1])
            }

            if(((i - 1) < grid.length) && (i - 1) >= 0) {
                queue.push([i-1, j])
            }
        }
    }
}

思路

与BFS同理。

时间空间复杂度

1. 时间复杂度：O(m*n)
2. 空间复杂度：O(m*n)