力扣200. 岛屿数量(BFS)

2024-06-02 08:04
文章标签 数量 力扣 200 bfs 岛屿

本文主要是介绍力扣200. 岛屿数量(BFS),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Problem: 200. 岛屿数量

文章目录

  • 题目描述
  • 思路及解法
  • 复杂度
  • Code

题目描述

在这里插入图片描述在这里插入图片描述

思路及解法

1.定义方向数组:定义一个方向数组 DIRECTIONS,表示上、下、左、右四个方向的移动。
2.获取网格的行数和列数同时初始化一个计数器 numIslands 用于记录岛屿的数量。
3.使用两层循环遍历整个网格,如果遇到一个未访问的陆地 ‘1’,计数器 numIslands 增加1,并调用 BFS 方法来标记整个岛屿。
4.BFS方法:

4.1.创建一个队列 queue,并将当前陆地的位置加入队列。
4.2.将当前陆地标记为已访问,即将 grid[row][col] 设置为 ‘0’。
4.3.使用一个循环处理队列中的每个位置,遍历四个遍历四个方向,根据方向数组计算新位置。如果新位置是有效的且为未访问的陆地 ‘1’,将其加入队列并标记为已访问。

复杂度

时间复杂度:

O ( M × N ) O(M \times N) O(M×N);其中 M M M N N N分别为举证grid的行数与列数

空间复杂度:

O ( M × N ) O(M \times N) O(M×N)

Code

class Solution {// Define four directions: up, down, left, and rightprivate static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};/*** Number of Islands** @param grid Given array* @return int*/public int numIslands(char[][] grid) {if (grid == null || grid.length == 0) {return 0;}int rows = grid.length;int cols = grid[0].length;int numIslands = 0;for (int row = 0; row < rows; row++) {for (int col = 0; col < cols; col++) {if (grid[row][col] == '1') {numIslands++;bfs(grid, row, col);}}}return numIslands;}/*** @param grid Given array* @param row  The row of array* @param col  The column of array*/private void bfs(char[][] grid, int row, int col) {int rows = grid.length;int cols = grid[0].length;Queue<int[]> queue = new LinkedList<>();queue.offer(new int[]{row, col});grid[row][col] = '0';  // Mark as accessedwhile (!queue.isEmpty()) {int[] current = queue.poll();int currentRow = current[0];int currentCol = current[1];for (int[] direction : DIRECTIONS) {int newRow = currentRow + direction[0];int newCol = currentCol + direction[1];if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && grid[newRow][newCol] == '1') {queue.offer(new int[]{newRow, newCol});grid[newRow][newCol] = '0';  // Mark as accessed}}}}
}

这篇关于力扣200. 岛屿数量(BFS)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1023399

相关文章

hdu1254(嵌套bfs,两次bfs)

/*第一次做这种题感觉很有压力,思路还是有点混乱,总是wa,改了好多次才ac的思路:把箱子的移动当做第一层bfs,队列节点要用到当前箱子坐标(x,y),走的次数step,当前人的weizhi(man_x,man_y),要判断人能否将箱子推到某点时要嵌套第二层bfs(人的移动);代码如下:

C#实战|大乐透选号器[6]:实现实时显示已选择的红蓝球数量

哈喽,你好啊,我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记,这是第6篇; 接下来实现实时显示当前选中红球数量,蓝球数量; 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时,在对应的位置显示实时已选择的红球、蓝球的数量; 02 标签名称 分别设置Label标签名称为:lblRedCount、lblBlueCount

poj 2195 bfs+有流量限制的最小费用流

题意: 给一张n * m(100 * 100)的图,图中” . " 代表空地, “ M ” 代表人, “ H ” 代表家。 现在,要你安排每个人从他所在的地方移动到家里,每移动一格的消耗是1,求最小的消耗。 人可以移动到家的那一格但是不进去。 解析: 先用bfs搞出每个M与每个H的距离。 然后就是网络流的建图过程了,先抽象出源点s和汇点t。 令源点与每个人相连,容量为1,费用为

POJ 3057 最大二分匹配+bfs + 二分

SampleInput35 5XXDXXX...XD...XX...DXXXXX5 12XXXXXXXXXXXXX..........DX.XXXXXXXXXXX..........XXXXXXXXXXXXX5 5XDXXXX.X.DXX.XXD.X.XXXXDXSampleOutput321impossible

深度优先(DFS)和广度优先(BFS)——算法

深度优先 深度优先搜索算法(英语:Depth-First-Search,DFS)是一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点,尽可能深的搜索树的分支,当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访

两数之和--力扣1

两数之和 题目思路C++代码 题目 思路 根据题目要求,元素不能重复且不需要排序,我们这里使用哈希表unordered_map。注意题目说了只对应一种答案。 所以我们在循环中,使用目标值减去当前循环的nums[i],得到差值,如果我们在map中能够找到这个差值,就说明存在两个整数的和为目标值。 如果没有找到,就将当前循环的nums[i]以及下标i放入map中,以便后续查

力扣第347题 前K个高频元素

前言 记录一下刷题历程 力扣第347题 前K个高频元素 前K个高频元素 原题目: 分析 我们首先使用哈希表来统计数字出现的频率,然后我们使用一个桶排序。我们首先定义一个长度为n+1的数组,对于下图这个示例就是长度为7的数组。为什么需要一个长度为n+1的数组呢?假如说总共有三个数字都为1,那么我们需要把这个1放在数组下标为3的位置,假如说数组长度为n,对于这个例子就是长度为3,那么它的

【数据结构与算法 | 灵神题单 | 删除链表篇】力扣3217, 82, 237

总结,删除链表节点问题使用到列表,哈希表,递归比较容易超时,我觉得使用计数排序比较稳,处理起来也不是很难。 1. 力扣3217:从链表中移除在数组中的节点 1.1 题目: 给你一个整数数组 nums 和一个链表的头节点 head。从链表中移除所有存在于 nums 中的节点后,返回修改后的链表的头节点。 示例 1: 输入: nums = [1,2,3], head = [1,2,3,

一个统计文件中关键词数量的小程序-优化版本

public class computeWxxFileNum{public static void main(String[] args) throws IOException {//读文件File sourceFile = new File("e:\\55-tmp\\xxx.log");FileReader in = new FileReader(sourceFile); LineNumber

一个统计文件中关键词数量的小程序

public class computeFileNum{public static void main(String[] args) throws IOException {File sourceFile = new File("e:\\55-tmp\\xxx.log"); FileReader in = new FileReader(sourceFile); LineNumberReader