汪图南
  • RAG

    • RAG
  • 快速入门
  • 高级技巧
前端面试之道
  • 打包工具

    • Webpack
    • Rollup
  • TypeScript

    • TypeScript基础
    • TypeScript类型挑战
  • CSS预编译器

    • SASS
  • 自动化测试

    • Vue应用测试
  • Vue2.0源码分析
  • Vue3.0源码分析
  • 数据结构和算法(基础)
  • LeetCode(刷题)
  • JavaScript书籍

    • 你不知道的JavaScript(上)
    • 你不知道的JavaScript(中下)
    • JavaScript数据结构和算法
    • JavaScript设计模式与开发实践
    • 深入理解ES6
  • Git书籍

    • 精通Git
Github
  • RAG

    • RAG
  • 快速入门
  • 高级技巧
前端面试之道
  • 打包工具

    • Webpack
    • Rollup
  • TypeScript

    • TypeScript基础
    • TypeScript类型挑战
  • CSS预编译器

    • SASS
  • 自动化测试

    • Vue应用测试
  • Vue2.0源码分析
  • Vue3.0源码分析
  • 数据结构和算法(基础)
  • LeetCode(刷题)
  • JavaScript书籍

    • 你不知道的JavaScript(上)
    • 你不知道的JavaScript(中下)
    • JavaScript数据结构和算法
    • JavaScript设计模式与开发实践
    • 深入理解ES6
  • Git书籍

    • 精通Git
Github
  • 介绍

    • 介绍
  • 推荐

    • LeetCode刷题推荐
  • 链表

    • 目录
    • 简单
    • 中等
    • 困难
  • 栈

    • 目录
    • 简单
    • 中等
    • 困难
  • 队列

    • 目录
    • 简单
    • 中等
    • 困难
  • 哈希表

    • 目录
    • 简单
    • 中等
    • 困难
  • 二叉树

    • 目录
    • 简单
    • 中等
    • 困难
  • 堆

    • 目录
    • 简单
    • 中等
    • 困难
  • 图

    • 目录
    • 简单
    • 中等
    • 困难
  • 搜索

    • 目录
    • 简单
    • 中等
    • 困难

中等

200.岛屿的数量

200.岛屿的数量

方法一:广度优先遍历BFS

// way1: 广度优先遍历
// m和n分别为矩阵行的数量和列的数量
// 时间复杂度:O(m * n)
// 空间复杂度:O(min(m, n)),最坏情况下遍历完整个矩阵
var bfs = (grid, i, j) => {
  const queue = [[i, j]];
  while (queue.length > 0) {
    const [i, j] = queue.shift();
    if (i >= 0 && j >= 0 && i < grid.length && j < grid[0].length && grid[i][j] === '1') {
      grid[i][j] = '0';
      queue.push([i + 1, j]);
      queue.push([i - 1, j]);
      queue.push([i, j + 1]);
      queue.push([i, j - 1]);
    }
  }
}
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') {
        bfs(grid, i, j);
        count++;
      }
    }
  }
  return count;
}
最后更新时间: 2025/5/6 15:36
贡献者: wangtunan
Prev
简单
Next
困难