leetcode Binary Tree Breadth-First Search

leetcode 200题

Posted by franki on September 6, 2021

leetcode 200题 岛屿数量

给你一个由 ’1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

示例 2：

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

思路

dfs

代码

 // 注意题意 连续大陆就是一个岛屿
 // 遍历二维数组，每当遇到1开启搜索模式，从当前节点向左/右/上/下，每次分别移动一步，如果是1则替换为0
var numIslands = function(grid) {
  function dfs(grid,i,j){
    // 递归终止条件
    if(i<0||i>=grid.length||j<0||j>=grid[0].length||grid[i][j]==='0'){
       return  
    }
    grid[i][j]='0' // 走过的标记为0
    dfs(grid, i + 1, j)
    dfs(grid, i, j + 1)
    dfs(grid, i - 1, j)
    dfs(grid, i, j - 1)
  }
  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'){
              dfs(grid,i,j)
              count++
          }
      }
  }
 return count
};

复杂度分析

  • 时间复杂度：O(N^2)
  • 空间复杂度：O(1)
CATALOG
    FEATURED TAGS
    前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析 生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python
    FRIENDS