DFS 解题

  • 首先看是否需要遍历所有节点，例如遍历二维数组就两层循环
  • 根据结果满足的条件进行递归
  • dfs 递归函数找到退出递归的判断条件
  • 标记成已到达防止循环

  • 根据题意不同方向去 dfs

    1. var numIslands = function(grid) {
    2.   const col = grid[0].length;
    3.   const row = grid.length;
    4.   let count = 0;
    5.   const dfs = (i, j) => {
    6.       if (i < 0 || i >= row || j < 0 || j >= col || grid[i][j] === '0') return
    7.       grid[i][j] = '0';
    8.       dfs(i, j + 1) || dfs(i, j - 1) || dfs(i + 1, j) || dfs(i - 1, j);
    9.   }
    10.   for(let i = 0; i < row; i++) {
    11.       for(let j = 0; j < col; j++) {
    12.           if (grid[i][j] === '1') {
    13.               count++;
    14.               dfs(i, j);
    15.           }
    16.       }
    17.   }
    18.   return count;
    19. };

    BFS 解题

  • 首先看是否需要遍历所有节点，例如遍历二维数组就两层循环

  • 定义队列
  • 根据结果满足的条件进行迭代
  • 队列先推入节点
  • 遍历队列的长度
  • 取出队列值
  • 找到边界直接退出，无需标记和 push 队列
  • 根据题意不同方向去标记和 push 队列
    1. var numIslands = function(grid) {
    2.   const col = grid[0].length;
    3.   const row = grid.length;
    4.   let count = 0;
    5.   let queue = [];
    6.   const dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    7.   for(let i = 0; i < row; i++) {
    8.       for(let j = 0; j < col; j++) {
    9.           if (grid[i][j] === '1') {
    10.               count++;
    11.               grid[i][j] = '0';
    12.               queue.push([i, j]);
    13.               while(queue.length) {
    14.                   const cur = queue.shift();
    15.                   for(const dir of dirs) {
    16.                       const x = cur[0] + dir[0];
    17.                       const y = cur[1] + dir[1];
    18.                       if (x < 0 || x >= row || y < 0 || y >= col || grid[x][y] === '0') continue
    19.                       grid[x][y] = '0';
    20.                       queue.push([x, y]);
    21.                   }
    22.               }
    23.           }
    24.       }
    25.   }
    26.   return count;
    27. };