当前位置: 首页 > news >正文

【经典算法】LeetCode 200. 岛屿数量(Java/C/Python3/Go实现含注释说明,中等)

目录

  • 题目描述
  • 思路及实现
    • 方式一:深度优先搜索(DFS)
      • 思路
      • 代码实现
        • Java版本
        • C语言版本
        • Python3版本
        • Golang版本
      • 复杂度分析
    • 方式二: 使用广度优先搜索(BFS)
      • 思路
      • 代码实现
        • Java实现
        • C++实现
        • Python3实现
        • Go实现
  • 总结
  • 相似题目

  • 标签(题目类型):深度优先搜索(DFS)、广度优先搜索(BFS)、并查集(Union Find)

题目描述

给定一个二维字符网格 map,'1' 表示陆地,'0' 表示水域。网格中的每个'1'都被视为一个岛屿的一部分,被水域包围的'1'(水平或垂直四个方向)形成岛屿。找出网格中岛屿的数量。

原题:LeetCode 200. 岛屿数量

思路及实现

方式一:深度优先搜索(DFS)

思路

使用深度优先搜索(DFS)遍历每个单元格,若遇到陆地’1’,则以该点作为起始点开始DFS,将与其相连的所有陆地都标记为已访问(例如,更改为’0’)。每次DFS表示遍历了一个完整的岛屿,岛屿数量加一。

代码实现

Java版本
public class Solution {private void dfs(char[][] grid, int i, int j) {int m = grid.length;int n = grid[0].length;// 判断边界条件和是否为陆地if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != '1') {return;}// 标记为已访问(水域)grid[i][j] = '0';// 递归访问上下左右四个方向的相邻陆地dfs(grid, i - 1, j); // 上dfs(grid, i + 1, j); // 下dfs(grid, i, j - 1); // 左dfs(grid, i, j + 1); // 右}public int numIslands(char[][] grid) {if (grid == null || grid.length == 0) {return 0;}int m = grid.length;int n = grid[0].length;int count = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == '1') {count++;dfs(grid, i, j);}}}return count;}
}

说明:Java版本使用递归的方式实现了DFS,并通过将已访问的陆地标记为’0’来避免重复计数。

C语言版本
#include <stdbool.h>void dfs(char** grid, int gridSize, int* gridColSize, int i, int j) {if (i < 0 || i >= gridSize || j < 0 || j >= gridColSize[0] || grid[i][j] == '0') {return;}grid[i][j] = '0'; // 标记为已访问dfs(grid, gridSize, gridColSize, i - 1, j); // 上dfs(grid, gridSize, gridColSize, i + 1, j); // 下dfs(grid, gridSize, gridColSize, i, j - 1); // 左dfs(grid, gridSize, gridColSize, i, j + 1); // 右
}int numIslands(char** grid, int gridSize, int* gridColSize){if (grid == NULL || gridSize == 0 || gridColSize[0] == 0) {return 0;}int count = 0;for (int i = 0; i < gridSize; i++) {for (int j = 0; j < gridColSize[0]; j++) {if (grid[i][j] == '1') {count++;dfs(grid, gridSize, gridColSize, i, j);}}}return count;
}

说明:C语言版本同样使用DFS,但需要注意二维数组的传递和边界条件的判断。

Python3版本
class Solution:def dfs(self, grid, i, j):if not 0 <= i < len(grid) or not 0 <= j < len(grid[0]) or grid[i][j] != '1':returngrid[i][j] = '0'  # 标记为已访问# 递归访问上下左右四个方向的相邻陆地self.dfs(grid, i - 1, j)  # 上self.dfs(grid, i + 1, j)  # 下self.dfs(grid, i, j - 1)  # 左self.dfs(grid, i, j + 1)  # 右def numIslands(self, grid: List[List[str]]) -> int:if not grid:return 0rows, cols = len(grid), len(grid[0])count = 0for i in range(rows):for j in range(cols):if grid[i][j] == '1':count += 1self.dfs(grid, i, j)return count

说明:Python3版本同样使用了DFS,但将DFS定义为了类方法,并处理了二维列表的边界条件和访问标记。

Golang版本
func dfs(grid [][]byte, i, j int) {rows, cols := len(grid), len(grid[0])if i < 0 || i >= rows || j < 0 || j >= cols || grid[i][j] != '1' {return}grid[i][j] = '0' // 标记为已访问// 递归访问上下左右四个方向的相邻陆地dfs(grid, i-1, j) // 上dfs(grid, i+1, j) // 下dfs(grid, i, j-1) // 左dfs(grid, i, j+1) // 右
}func numIslands(grid [][]byte) int {if len(grid) == 0 {return 0}rows, cols := len(grid), len(grid[0])count := 0for i := 0; i < rows; i++ {for j := 0; j < cols; j++ {if grid[i][j] == '1' {count++dfs(grid, i, j)}}}return count
}

说明:Golang版本同样使用了DFS算法,但注意在Go中二维数组(切片)的传递和边界条件判断。

复杂度分析

  • 时间复杂度:O(mn),其中m和n分别是网格的行数和列数。因为我们需要遍历整个网格一次,并且在每个陆地上都执行DFS操作,DFS操作的时间复杂度取决于与当前陆地相连的其他陆地的数量,但最坏情况下会遍历完整个网格,因此总的时间复杂度是O(mn)。
  • 空间复杂度:O(mn)(DFS栈空间)。在最坏的情况下,整个网格都是陆地,并且所有陆地都相互连接,此时DFS的递归调用栈会达到最大深度,即网格的面积mn。然而,在平均情况下,空间复杂度会远小于O(mn),因为大多数DFS调用都会在遇到水域时返回。

方式二: 使用广度优先搜索(BFS)

思路

与DFS类似,BFS也通过遍历网格来寻找岛屿。但BFS通常使用队列来存储待访问的节点(在这里是网格中的位置)。当一个陆地(‘1’)被访问时,我们将其标记为已访问(如’0’),并将其四个相邻的陆地(如果存在)加入队列中。我们继续从队列中取出节点,直到队列为空,这意味着我们已经探索了一个完整的岛屿。然后,我们重复这个过程,直到所有的陆地都被访问过。

代码实现

Java实现
import java.util.LinkedList;
import java.util.Queue;public class Solution {public int numIslands(char[][] grid) {if (grid == null || grid.length == 0) return 0;int count = 0;int m = grid.length;int n = grid[0].length;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == '1') {count++;bfs(grid, i, j);}}}return count;}private void bfs(char[][] grid, int row, int col) {int m = grid.length;int n = grid[0].length;// 定义上下左右四个方向的偏移量int[] dx = {-1, 1, 0, 0};int[] dy = {0, 0, -1, 1};// 使用队列存储待访问的节点Queue<int[]> queue = new LinkedList<>();queue.offer(new int[]{row, col});// 标记当前节点为已访问grid[row][col] = '0';while (!queue.isEmpty()) {int[] curr = queue.poll();int x = curr[0];int y = curr[1];// 遍历四个方向for (int i = 0; i < 4; i++) {int nx = x + dx[i];int ny = y + dy[i];// 检查是否越界和是否为陆地且未访问if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == '1') {// 标记为已访问并加入队列grid[nx][ny] = '0';queue.offer(new int[]{nx, ny});}}}}
}
C++实现
#include <queue>
#include <vector>using namespace std;void bfs(vector<vector<char>>& grid, int i, int j) {int m = grid.size();int n = grid[0].size();// 定义上下左右四个方向的偏移量vector<int> dx = {-1, 1, 0, 0};vector<int> dy = {0, 0, -1, 1};// 使用队列存储待访问的节点queue<pair<int, int>> q;q.push({i, j});// 标记当前节点为已访问grid[i][j] = '0';while (!q.empty()) {auto curr = q.front();q.pop();int x = curr.first;int y = curr.second;// 遍历四个方向for (int k = 0; k < 4; k++) {int nx = x + dx[k];int ny = y + dy[k];// 检查是否越界和是否为陆地且未访问if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == '1') {// 标记为已访问并加入队列grid[nx][ny] = '0';q.push({nx, ny});}}}
}int numIslands(vector<vector<char>>& grid) {if (grid.empty()) return 0;int m = grid.size();int n = grid[0].size();int count = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == '1') {count++;bfs(grid, i, j);}}}return count;
}
Python3实现
from collections import dequedef bfs(grid, row, col):m, n = len(grid), len(grid[0])directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]  # 右,左,下,上queue = deque([(row, col)])grid[row][col] = 0  # 标记为已访问while queue:x, y = queue.popleft()for dx, dy in directions:nx, ny = x + dx, y + dyif 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == '1':grid[nx][ny] = 0  # 标记为已访问queue.append((nx, ny))def numIslands(grid):if not grid:return 0m, n = len(grid), len(grid[0])count = 0for i in range(m):for j in range(n):if grid[i][j] == '1':count += 1bfs(grid, i, j)return count
Go实现
package mainimport ("container/list"
)type Point struct {X, Y int
}func bfs(grid [][]byte, row, col int) {m, n := len(grid), len(grid[0])directions := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}} // 上,下,左,右queue := list.New()queue.PushBack(Point{row, col})grid[row][col] = '0' // 标记为已访问for queue.Len() > 0 {curr := queue.Front().Value.(Point)queue.Remove(queue.Front())for _, dir := range directions {nx, ny := curr.X+dir[0], curr.

总结

方式优点缺点时间复杂度空间复杂度
DFS实现简单,容易理解在最坏情况下,空间复杂度较高O(mn)O(mn)(DFS栈空间)

相似题目

相似题目难度链接
LeetCode 695. 岛屿的最大面积中等LeetCode链接
LeetCode 130. 被围绕的区域中等LeetCode链接
[LeetCode 1254. 统计封闭岛屿的数目

相关文章:

【经典算法】LeetCode 200. 岛屿数量(Java/C/Python3/Go实现含注释说明,中等)

目录 题目描述思路及实现方式一&#xff1a;深度优先搜索&#xff08;DFS&#xff09;思路代码实现Java版本C语言版本Python3版本Golang版本 复杂度分析 方式二&#xff1a; 使用广度优先搜索&#xff08;BFS&#xff09;思路代码实现Java实现C实现Python3实现Go实现 总结相似题…...

Hive SQL-DQL-Select查询语句用法详解

HQL Select用法详解 1.基础语法 &#xff08;1&#xff09;select_exp &#xff08;2&#xff09;ALL、DISTINCT &#xff08;3&#xff09;WHERE &#xff08;4&#xff09;分区查询、分区裁剪 &#xff08;5&#xff09;GROUP BY &#xff08;6&#xff09;HAVING &#xff0…...

沙盘Sandboxie v5.56.4

菜鸟高手裸奔工具沙盘Sandboxie是一款国外著名的系统安全工具&#xff0c;它可以让选定程序在安全的隔离环境下运行&#xff0c; 只要在此环境中运行的软件&#xff0c;浏览器或注册表信息等都可以完整的进行清空&#xff0c;不留一点痕迹。同时可以防御些 带有木马或者病毒的…...

Arcpy开发记录

一.GDB数据库相关 1.单独的shape更新时&#xff0c;不会有限制&#xff0c;数据会自动截取 2.在GDB下&#xff0c;使用UpdateCursor更新字段时&#xff0c;填入的数据长度必须与字段长度要求一致&#xff0c;否则报错&#xff1a; 二.Cursor相关 嵌套使用cursor时&#xff0c…...

Android使用itextpdf操作PDF文档

1、导入jar包&#xff1a; itext-asian.jaritextpdf-5.5.8.jar Paragraph 和 Phrase 的区别&#xff1a; 在 iTextPDF 库中&#xff0c;Paragraph 和 Phrase 是用于创建和组织文本内容的两个不同的类。 Paragraph&#xff08;段落&#xff09;&#xff1a; Paragraph 是一个…...

llama_index微调BGE模型

微调模型是为了让模型在特殊领域表现良好,帮助其学习到专业术语等。 本文采用llama_index框架微调BGE模型,跑通整个流程,并学习模型微调的方法。 已开源:https://github.com/stay-leave/enhance_llm 一、环境准备 Linux环境,GPU L20 48G,Python3.8.10。 pip该库即可。…...

什么是限流?常见的限流算法

目录 1. 什么是限流 2. 常见限流算法 3. 固定窗口算法 4. 滑动窗口算法 5. 漏桶算法 6. 令牌桶算法 7. 限流算法选择 1. 什么是限流 限流&#xff08;Rate Limiting&#xff09;是一种应用程序或系统资源管理的策略&#xff0c;用于控制对某个服务、接口或功能的访问速…...

ZL-0895小动物活动记录仪可同时检测8只动物的活动量

简单介绍&#xff1a; 小动物活动记录仪是一种多用途、宽范围的小动物活动记录仪器&#xff0c;可用于小鼠、大鼠、豚鼠和兔的实验&#xff0c;小动物活动记录仪​具有不需对动物使用特别盛具的特点&#xff0c;可在不改变动物原生活环境的情况下&#xff0c;进行实时监测&…...

注册测绘师的前世今生

本文梳理了 注册测绘师 的前世今生&#xff0c;具体情况如下表&#xff1a; 历史线时间事件诞生2007年1月原人事部、国家测绘局联合印发《注册测绘师制度暂行规定》&#xff0c;注册测绘师制度建立。同时同步发布《注册测绘师资格考试实施办法》、《注册测绘师资格考核认定办法…...

Python中的异常处理:深入探索try-except-finally结构

Python中的异常处理&#xff1a;深入探索try-except-finally结构 一、引言 在Python编程中&#xff0c;异常处理是一个非常重要的部分。当程序遇到错误时&#xff0c;比如尝试除以零、文件读取失败等&#xff0c;Python会抛出一个异常。如果我们不捕获这些异常&#xff0c;程…...

【R语言】边缘概率密度图

边缘概率密度图是一种在多变量数据分析中常用的图形工具&#xff0c;用于显示每个单独变量的概率密度估计。它通常用于散点图的边缘&#xff0c;以便更好地理解单个变量的分布情况&#xff0c;同时保留了散点图的相关性信息。 在边缘概率密度图中&#xff0c;每个变量的概率密度…...

中国结(科普)

中国结是一种手工编织工艺品&#xff0c;它身上所显示的情致与智慧正是汉族古老文明中的一个侧面。 [1]它原本是由旧石器时代的缝衣打结&#xff0c;后推展至汉朝的仪礼记事&#xff0c;再演变成今日的装饰手艺。周朝人随身的佩戴玉常以中国结为装饰&#xff0c;而战国时代的铜…...

使用Android Studio 搭建AOSP FrameWork 源码阅读开发环境

文章目录 概述安装Android Studio编译源码使用Android Studio打开源码制作ipr文件直接编译成功后自动打开Android Studio 修改SystemUI验证开发环境 概述 我们都知道Android的系统源码量非常之大&#xff0c;大致有frameworka层源码&#xff0c;硬件层(HAL)源码&#xff0c;内…...

区块链 | IPFS:CID

&#x1f98a;原文&#xff1a;Anatomy of a CID &#x1f98a;写在前面&#xff1a;本文属于搬运博客&#xff0c;自己留存学习。 1 CID 在分布式网络中与其他节点交换数据时&#xff0c;我们依赖于内容寻址&#xff08;而不是中心化网络的位置寻址&#xff09;来安全地定位…...

PostgreSQL(十二)报错:Tried to send an out-of-range integer as a 2-byte value: 51000

目录 一、报错场景二、源码分析三、实际原因&#xff08;更加复杂&#xff09;四、解决思路 一、报错场景 今天写了一个历史数据处理程序&#xff0c;在开发环境、测试环境都可以正常执行&#xff0c;但是放到生产环境上就不行&#xff0c;报了一个这样的错误&#xff1a; or…...

Linux守护进程

进程组和会话在 UNIX 系统中是非常重要的概念&#xff0c;特别是在进行作业控制和终端会话管理时。下面是关于进程组和会话的详细解释&#xff1a; 进程组&#xff08;Process Group&#xff09; 定义与作用&#xff1a; 进程组是一个或多个进程的集合&#xff0c;这些进程通常…...

HarmonyOS 应用开发——入门

首先当然是华为的官方文档了&#xff0c;要认真学习: https://developer.huawei.com/consumer/cn/doc/harmonyos-guides-V2/start-overview-0000001478061421-V2 不想花时间看&#xff0c;可以看我下面总结的干货&#xff0c;哈哈 第一个问题&#xff1a;stage架构和fa架构的区…...

开源免费的发票识别OCR应用:Invoice

Invoice&#xff1a;轻松识别&#xff0c;发票电子化扫描烦恼消- 精选真开源&#xff0c;释放新价值。 概览 Invoice 是github社区上一个采用开源许可协议发布的增值税发票光学字符识别&#xff08;OCR&#xff09;解决方案项目。该项目不仅集成了预训练的高级模型&#xff0c…...

关于Docker alpine

1.拉取alpine镜像 docker pull alpine 2.运行镜像成为容器 docker run -it --rm alpine sh (--rm标志确保容器在退出时被自动删除。) 3.容器建立后&#xff0c;运行 docker exec -it <container_id> sh 4.进入容器里的 alpine环境 ①.配置安装源 cat >/etc…...

【Elasticsearch运维系列】Elasticsearch7.12.1启动指定版本JDK:你学废了吗?

一、背景 一套生ES集群&#xff0c;版本为7.12.1&#xff0c;近期频繁告警&#xff0c;频繁出现索引分片异常&#xff0c;索引状态异常&#xff0c;导致应用无法正常写入ES&#xff0c;另外&#xff0c;也经常出现节点掉问题。通过分析相关ES日志&#xff0c;显示和当前JAVA G…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

【JVM】- 内存结构

引言 JVM&#xff1a;Java Virtual Machine 定义&#xff1a;Java虚拟机&#xff0c;Java二进制字节码的运行环境好处&#xff1a; 一次编写&#xff0c;到处运行自动内存管理&#xff0c;垃圾回收的功能数组下标越界检查&#xff08;会抛异常&#xff0c;不会覆盖到其他代码…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...

人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式

今天是关于AI如何在教学中增强学生的学习体验&#xff0c;我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育&#xff0c;这并非炒作&#xff0c;而是已经发生的巨大变革。教育机构和教育者不能忽视它&#xff0c;试图简单地禁止学生使…...

MFC 抛体运动模拟:常见问题解决与界面美化

在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...

Windows安装Miniconda

一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...

宇树科技,改名了!

提到国内具身智能和机器人领域的代表企业&#xff0c;那宇树科技&#xff08;Unitree&#xff09;必须名列其榜。 最近&#xff0c;宇树科技的一项新变动消息在业界引发了不少关注和讨论&#xff0c;即&#xff1a; 宇树向其合作伙伴发布了一封公司名称变更函称&#xff0c;因…...

群晖NAS如何在虚拟机创建飞牛NAS

套件中心下载安装Virtual Machine Manager 创建虚拟机 配置虚拟机 飞牛官网下载 https://iso.liveupdate.fnnas.com/x86_64/trim/fnos-0.9.2-863.iso 群晖NAS如何在虚拟机创建飞牛NAS - 个人信息分享...

Unity UGUI Button事件流程

场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...