【经典算法】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实现含注释说明,中等)
目录 题目描述思路及实现方式一:深度优先搜索(DFS)思路代码实现Java版本C语言版本Python3版本Golang版本 复杂度分析 方式二: 使用广度优先搜索(BFS)思路代码实现Java实现C实现Python3实现Go实现 总结相似题…...
Hive SQL-DQL-Select查询语句用法详解
HQL Select用法详解 1.基础语法 (1)select_exp (2)ALL、DISTINCT (3)WHERE (4)分区查询、分区裁剪 (5)GROUP BY (6)HAVING ࿰…...
沙盘Sandboxie v5.56.4
菜鸟高手裸奔工具沙盘Sandboxie是一款国外著名的系统安全工具,它可以让选定程序在安全的隔离环境下运行, 只要在此环境中运行的软件,浏览器或注册表信息等都可以完整的进行清空,不留一点痕迹。同时可以防御些 带有木马或者病毒的…...
Arcpy开发记录
一.GDB数据库相关 1.单独的shape更新时,不会有限制,数据会自动截取 2.在GDB下,使用UpdateCursor更新字段时,填入的数据长度必须与字段长度要求一致,否则报错: 二.Cursor相关 嵌套使用cursor时,…...
Android使用itextpdf操作PDF文档
1、导入jar包: itext-asian.jaritextpdf-5.5.8.jar Paragraph 和 Phrase 的区别: 在 iTextPDF 库中,Paragraph 和 Phrase 是用于创建和组织文本内容的两个不同的类。 Paragraph(段落): 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. 什么是限流 限流(Rate Limiting)是一种应用程序或系统资源管理的策略,用于控制对某个服务、接口或功能的访问速…...
ZL-0895小动物活动记录仪可同时检测8只动物的活动量
简单介绍: 小动物活动记录仪是一种多用途、宽范围的小动物活动记录仪器,可用于小鼠、大鼠、豚鼠和兔的实验,小动物活动记录仪具有不需对动物使用特别盛具的特点,可在不改变动物原生活环境的情况下,进行实时监测&…...
注册测绘师的前世今生
本文梳理了 注册测绘师 的前世今生,具体情况如下表: 历史线时间事件诞生2007年1月原人事部、国家测绘局联合印发《注册测绘师制度暂行规定》,注册测绘师制度建立。同时同步发布《注册测绘师资格考试实施办法》、《注册测绘师资格考核认定办法…...
Python中的异常处理:深入探索try-except-finally结构
Python中的异常处理:深入探索try-except-finally结构 一、引言 在Python编程中,异常处理是一个非常重要的部分。当程序遇到错误时,比如尝试除以零、文件读取失败等,Python会抛出一个异常。如果我们不捕获这些异常,程…...
【R语言】边缘概率密度图
边缘概率密度图是一种在多变量数据分析中常用的图形工具,用于显示每个单独变量的概率密度估计。它通常用于散点图的边缘,以便更好地理解单个变量的分布情况,同时保留了散点图的相关性信息。 在边缘概率密度图中,每个变量的概率密度…...
中国结(科普)
中国结是一种手工编织工艺品,它身上所显示的情致与智慧正是汉族古老文明中的一个侧面。 [1]它原本是由旧石器时代的缝衣打结,后推展至汉朝的仪礼记事,再演变成今日的装饰手艺。周朝人随身的佩戴玉常以中国结为装饰,而战国时代的铜…...
使用Android Studio 搭建AOSP FrameWork 源码阅读开发环境
文章目录 概述安装Android Studio编译源码使用Android Studio打开源码制作ipr文件直接编译成功后自动打开Android Studio 修改SystemUI验证开发环境 概述 我们都知道Android的系统源码量非常之大,大致有frameworka层源码,硬件层(HAL)源码,内…...
区块链 | IPFS:CID
🦊原文:Anatomy of a CID 🦊写在前面:本文属于搬运博客,自己留存学习。 1 CID 在分布式网络中与其他节点交换数据时,我们依赖于内容寻址(而不是中心化网络的位置寻址)来安全地定位…...
PostgreSQL(十二)报错:Tried to send an out-of-range integer as a 2-byte value: 51000
目录 一、报错场景二、源码分析三、实际原因(更加复杂)四、解决思路 一、报错场景 今天写了一个历史数据处理程序,在开发环境、测试环境都可以正常执行,但是放到生产环境上就不行,报了一个这样的错误: or…...
Linux守护进程
进程组和会话在 UNIX 系统中是非常重要的概念,特别是在进行作业控制和终端会话管理时。下面是关于进程组和会话的详细解释: 进程组(Process Group) 定义与作用: 进程组是一个或多个进程的集合,这些进程通常…...
HarmonyOS 应用开发——入门
首先当然是华为的官方文档了,要认真学习: https://developer.huawei.com/consumer/cn/doc/harmonyos-guides-V2/start-overview-0000001478061421-V2 不想花时间看,可以看我下面总结的干货,哈哈 第一个问题:stage架构和fa架构的区…...
开源免费的发票识别OCR应用:Invoice
Invoice:轻松识别,发票电子化扫描烦恼消- 精选真开源,释放新价值。 概览 Invoice 是github社区上一个采用开源许可协议发布的增值税发票光学字符识别(OCR)解决方案项目。该项目不仅集成了预训练的高级模型,…...
关于Docker alpine
1.拉取alpine镜像 docker pull alpine 2.运行镜像成为容器 docker run -it --rm alpine sh (--rm标志确保容器在退出时被自动删除。) 3.容器建立后,运行 docker exec -it <container_id> sh 4.进入容器里的 alpine环境 ①.配置安装源 cat >/etc…...
【Elasticsearch运维系列】Elasticsearch7.12.1启动指定版本JDK:你学废了吗?
一、背景 一套生ES集群,版本为7.12.1,近期频繁告警,频繁出现索引分片异常,索引状态异常,导致应用无法正常写入ES,另外,也经常出现节点掉问题。通过分析相关ES日志,显示和当前JAVA G…...
Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动
一、前言说明 在2011版本的gb28181协议中,拉取视频流只要求udp方式,从2016开始要求新增支持tcp被动和tcp主动两种方式,udp理论上会丢包的,所以实际使用过程可能会出现画面花屏的情况,而tcp肯定不丢包,起码…...
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以? 在 Golang 的面试中,map 类型的使用是一个常见的考点,其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...
跨链模式:多链互操作架构与性能扩展方案
跨链模式:多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈:模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展(H2Cross架构): 适配层…...
【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)
1.获取 authorizationCode: 2.利用 authorizationCode 获取 accessToken:文档中心 3.获取手机:文档中心 4.获取昵称头像:文档中心 首先创建 request 若要获取手机号,scope必填 phone,permissions 必填 …...
RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程
本文较长,建议点赞收藏,以免遗失。更多AI大模型应用开发学习视频及资料,尽在聚客AI学院。 本文全面剖析RNN核心原理,深入讲解梯度消失/爆炸问题,并通过LSTM/GRU结构实现解决方案,提供时间序列预测和文本生成…...
大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计
随着大语言模型(LLM)参数规模的增长,推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长,而KV缓存的内存消耗可能高达数十GB(例如Llama2-7B处理100K token时需50GB内存&a…...
OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...
SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)
上一章用到了V2 的概念,其实 Fiori当中还有 V4,咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务),代理中间件(ui5-middleware-simpleproxy)-CSDN博客…...
服务器--宝塔命令
一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行! sudo su - 1. CentOS 系统: yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...
虚拟电厂发展三大趋势:市场化、技术主导、车网互联
市场化:从政策驱动到多元盈利 政策全面赋能 2025年4月,国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》,首次明确虚拟电厂为“独立市场主体”,提出硬性目标:2027年全国调节能力≥2000万千瓦࿰…...
