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

代码随想录-算法训练营-番外(图论02:岛屿数量,岛屿的最大面积)

day02 图论part02
今日任务:岛屿数量,岛屿的最大面积
都是一个模子套出来的
https://programmercarl.com/kamacoder/0099.岛屿的数量深搜.html#思路往日任务:
day01 图论part01 
今日任务:图论理论基础/所有可到达的路径
代码随想录图论视频部分还没更新
https://programmercarl.com/kamacoder/图论理论基础.html#图的基本概念

day02

岛屿数量

dfs

 import java.util.Scanner;​public class Main{public static int[][] dir ={{0,1},{1,0},{-1,0},{0,-1}};public static void main(String[] args){Scanner sc = new Scanner(System.in);int m = sc.nextInt();int n = sc.nextInt();int[][] grid = new int[m][n];for(int i = 0 ; i < m; i++){for(int j = 0; j < n; j++){grid[i][j] = sc.nextInt();}}boolean[][] visited = new boolean[m][n];int count = 0;for(int i = 0 ; i < m; i++){for(int j = 0; j < n; j++){if( visited[i][j] == false && grid[i][j] == 1){count++;visited[i][j] = true;//访问过了dfs(grid,i,j,visited);//一直找临近陆地直到找不到}}}System.out.println(count);}private static void dfs(int[][] grid,int x,int y,boolean[][] visited){for(int i = 0; i < 4; i++){//x += dir[i][0];//这里错了,x和y需要用四次,可是刚用一次值就改变了//y += dir[i][1];int x1 = x + dir[i][0];int y1 = y + dir[i][1];if(x1<0||y1<0||x1>= grid.length||y1>=grid[0].length)continue;//越界则继续判断下一个旁边的位置if(!visited[x1][y1] && grid[x1][y1]==1)//旁边是没遇到过的陆地{visited[x1][y1]=true;dfs(grid,x1,y1,visited);//继续找临近陆地}}}}

bfs

main方法一样,dfs和bfs有细微的差别,dfs是遇到陆地就递归直到越界,bfs是遇到陆地就加到queue里面直到queue为空

linkedlist实现queue,用到了isEmpty方法,peek方法和poll方法

 import java.util.*;public class Main {public static int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};//下右上左逆时针遍历​public static void bfs(int[][] grid, boolean[][] visited, int x, int y) {Queue<pair> queue = new LinkedList<pair>();//定义坐标队列,没有现成的pair类,在下面自定义了queue.add(new pair(x, y));//第一个位置入队visited[x][y] = true;//遇到入队直接标记为优先,// 否则出队时才标记的话会导致重复访问,比如下方节点会在右下顺序的时候被第二次访问入队while (!queue.isEmpty()) {int curX = queue.peek().first;int curY = queue.poll().second;//当前横纵坐标for (int i = 0; i < 4; i++) {//顺时针遍历新节点next,下面记录坐标int nextX = curX + dir[i][0];int nextY = curY + dir[i][1];if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) {continue;}//去除越界部分if (!visited[nextX][nextY] && grid[nextX][nextY] == 1) {queue.add(new pair(nextX, nextY));visited[nextX][nextY] = true;//逻辑同上}}}}​public static void main(String[] args) {Scanner sc = new Scanner(System.in);int m = sc.nextInt();int n = sc.nextInt();int[][] grid = new int[m][n];boolean[][] visited = new boolean[m][n];int ans = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {grid[i][j] = sc.nextInt();}}for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (!visited[i][j] && grid[i][j] == 1) {ans++;bfs(grid, visited, i, j);}}}System.out.println(ans);}// 定义 pair 类来表示坐标public static class pair {int first; // 横坐标int second; // 纵坐标​// 构造函数public pair(int x, int y) {this.first = x;this.second = y;}}}

岛屿的最大面积

dfs

套岛屿数量的模板,变化很少(话说这道题怎么没有答案啊)

 import java.util.Scanner;public class Main{public static int count;//这里变了public static int[][] dir ={{0,1},{1,0},{-1,0},{0,-1}};public static void main(String[] args){Scanner sc = new Scanner(System.in);int m = sc.nextInt();int n = sc.nextInt();int[][] grid = new int[m][n];for(int i = 0 ; i < m; i++){for(int j = 0; j < n; j++){grid[i][j] = sc.nextInt();}}boolean[][] visited = new boolean[m][n];int result = 0;//这里变了for(int i = 0 ; i < m; i++){for(int j = 0; j < n; j++){if( visited[i][j] == false && grid[i][j] == 1){count = 1;visited[i][j] = true;dfs(grid,i,j,visited);result = Math.max(result, count);//这里变了}}}System.out.println(result);//这里变了}private static void dfs(int[][] grid,int x,int y,boolean[][] visited){for(int i = 0; i < 4; i++){int x1 = x + dir[i][0];int y1 = y + dir[i][1];if(x1<0||y1<0||x1>= grid.length||y1>=grid[0].length)continue;if(!visited[x1][y1] && grid[x1][y1]==1){visited[x1][y1]=true;count++;//这里变了dfs(grid,x1,y1,visited);}}}}

bfs

套模版,基本没变化

 import java.util.*;​public class Main {public static int count;//多了这一行public static int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};​public static void bfs(int[][] grid, boolean[][] visited, int x, int y) {Queue<pair> queue = new LinkedList<pair>();queue.add(new pair(x, y));visited[x][y] = true;​while (!queue.isEmpty()) {int curX = queue.peek().first;int curY = queue.poll().second;for (int i = 0; i < 4; i++) {int nextX = curX + dir[i][0];int nextY = curY + dir[i][1];if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) {continue;}if (!visited[nextX][nextY] && grid[nextX][nextY] == 1) {queue.add(new pair(nextX, nextY));visited[nextX][nextY] = true;count++;//多了这一行}}}}​public static void main(String[] args) {Scanner sc = new Scanner(System.in);int m = sc.nextInt();int n = sc.nextInt();int[][] grid = new int[m][n];boolean[][] visited = new boolean[m][n];int result = 0;//这里for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {grid[i][j] = sc.nextInt();}}for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (!visited[i][j] && grid[i][j] == 1) {count = 1;bfs(grid, visited, i, j);result = Math.max(result, count);//这里}}}System.out.println(result);}public static class pair {int first; int second;public pair(int x, int y) {this.first = x;this.second = y;}}}

感谢大佬分享:

代码随想录算法训练营第五十一天|Day51 图论-CSDN博客

相关文章:

代码随想录-算法训练营-番外(图论02:岛屿数量,岛屿的最大面积)

day02 图论part02 今日任务:岛屿数量,岛屿的最大面积 都是一个模子套出来的 https://programmercarl.com/kamacoder/0099.岛屿的数量深搜.html#思路往日任务: day01 图论part01 今日任务:图论理论基础/所有可到达的路径 代码随想录图论视频部分还没更新 https://programmercar…...

20 go语言(golang) - gin框架安装及使用(一)

一、简介 Gin是一个用Go语言编写的高性能Web框架&#xff0c;专注于构建快速、可靠的HTTP服务。它以其速度和简洁性而闻名&#xff0c;非常适合用于开发RESTful API。 高性能&#xff1a;Gin使用了httprouter进行路由管理&#xff0c;这是一个轻量级且非常快速的HTTP请求路由器…...

重生之我在学Vue--第3天 Vue 3 模板语法与指令

重生之我在学Vue–第3天 Vue 3 模板语法与指令 文章目录 重生之我在学Vue--第3天 Vue 3 模板语法与指令前言一、数据绑定1.1 单向绑定1.2 双向绑定 二、常用指令2.1 v-bind2.2 v-model2.3 v-if2.4 v-show2.5 v-for2.6 v-on 三、事件处理与表单绑定3.1 事件处理3.2 表单绑定 前言…...

电脑win11家庭版升级专业版和企业版相关事项

我的是零刻ser9&#xff0c;自带win11家庭版&#xff0c;但是我有远程操控需求&#xff0c;想用windows系统自带的远程连接功能&#xff0c;所以需要升级为专业版。然后在系统激活页面通过更改序列号方式&#xff0c;淘宝几块钱买了个序列号升级成功专业版了。但是&#xff0c;…...

docker 架构详解

Docker架构是基于客户端-服务器&#xff08;C/S&#xff09;模式的&#xff0c;包含多个关键组件&#xff0c;以确保容器化应用的高效构建、管理和运行。以下是对Docker架构的详细解析&#xff1a; Docker 架构概述 Docker 架构采用客户端-服务器&#xff08;C/S&#xff09;…...

tinyCam Pro 用于远程监控,控制和录制您的私人公共网络或IP摄像机

tinyCam Pro 是一款用于远程监控&#xff0c;控制和录制您的私人/公共网络或IP摄像机&#xff0c;视频编码器和具有500万次下载的CCTV摄像头的DVR。需使用3G/4G/WiFi连接和下载数据。 tinyCam Monitor Pro 可用于远程安全地监控您的宝宝、宠物、家庭、商业、交通和天气&#xf…...

Flask 验证码自动生成

Flask 验证码自动生成 想必验证码大家都有所了解&#xff0c;但是可以自己定义图片验证码&#xff0c;包含数字&#xff0c;英文以及数字计算&#xff0c;自动生成验证码。 生成图片以及结果 from captcha.image import ImageCaptchafrom PIL import Image from random impo…...

vmpwn小总结

前言&#xff1a; 好久没有更新博客了&#xff0c;关于vm的学习也是断断续续的&#xff0c;只见识了几道题目&#xff0c;但是还是想总结一下&#xff0c;所谓vmpwn就是把出栈&#xff0c;进栈&#xff0c;寄存器&#xff0c;bss段等单独申请一块空闲实现相关的功能&#xff0…...

开源密码管理器 Bitwarden 一站式管理所有密码以及 2FA

本文首发于只抄博客&#xff0c;欢迎点击原文链接了解更多内容。 前言 随着注册的平台越来越多&#xff0c;管理密码的难度也越来越高了。要是把密码都设置成一样的&#xff0c;担心哪天某个平台泄露被一锅端&#xff0c;而每个平台单独一个密码又不太好记&#xff0c;这时候就…...

标准体重计算API集成指南

标准体重计算API集成指南 引言 在当今数字化和健康意识日益增长的时代&#xff0c;开发人员和健康管理专业人士不断寻找创新的方法来促进用户的健康生活。标准体重计算是一个关键的健康指标&#xff0c;它可以帮助个人了解自己的身体状况&#xff0c;并为制定合适的饮食和运动…...

多个终端查看的history不一样,如何确保多个终端会话之间的 history 一致,减少历史记录差异

问题&#xff1a; 在使用 Linux 系统时&#xff0c;history 命令显示的历史记录通常是与当前终端会话相关的。这就意味着&#xff0c;如果你在多个终端中打开会话&#xff0c;它们显示的历史记录可能不完全相同。这个问题通常是由以下原因引起的&#xff1a; 原因&#xff1a…...

Spring Boot整合EasyExcel并行导出及Zip压缩下载

1. 项目依赖 首先&#xff0c;我们需要引入相关的依赖&#xff0c;包括 Spring Boot 和阿里巴巴的 EasyExcel 组件&#xff0c;此外还需要使用 Java 的 Zip 工具进行压缩操作。 <dependencies><!-- Spring Web --><dependency><groupId>org.springfr…...

Docker 对 iptables 规则的自动配置,这句话是什么意思

Docker 对 iptables 规则的自动配置指的是 Docker 守护进程 (daemon) 会自动管理 Linux 系统上的 iptables 规则&#xff0c;以便容器可以正确地进行网络通信。这对于大多数用户来说是一个方便的功能&#xff0c;因为它简化了容器网络配置。 具体来说&#xff0c;这意味着&…...

使用aarch64-unknown-linux-musl编译生成静态ARM64可执行文件

使用aarch64-unknown-linux-musl编译生成静态ARM64可执行文件 使用aarch64-unknown-linux-musl编译生成静态ARM64可执行文件1. 安装aarch64-unknown-linux-musl目标2. 安装交叉编译工具链安装musl-cross-make 3. 配置Rust编译器使用交叉编译工具链4. 编译你的Rust项目5. 运行或…...

【SpringBoot中出现循环依赖错误】

SpringBoot中出现循环依赖错误 在Spring Boot中&#xff0c;循环依赖&#xff08;circular dependency&#xff09;是指两个或多个bean相互依赖&#xff0c;形成一个闭合的依赖环。例如&#xff0c;Bean A依赖于Bean B&#xff0c;而Bean B又反过来依赖于Bean A。这种情况下&a…...

数据仓库-基于角色的权限管理(RBAC)

什么是基于角色的用户管理&#xff1f; 基于角色的用户管理(Role-Based Access Control&#xff0c;简称RBAC)是通过为角色赋予权限&#xff0c;用户通过成为适当的角色而得到这些角色的权限。 角色是一组权限的抽象。 使用RBAC可以极大简化对权限的管理。 什么是RBAC模型&…...

springboot3整合javafx解决bean注入问题

springboot整合javafx时候&#xff0c;很多问题就在于controller没有被spring容器管理&#xff0c;无法注入bean&#xff0c;在这里提供一套自己的解决思路 执行逻辑 这里仅仅提供一个演示&#xff0c;我点击按钮之后&#xff0c;从service层返回一个文本并显示 项目结构 创…...

.NET 8 Blazor Web项目中的 .razor 文件与 .cshtml 文件的本质区别

在.NET 8 Blazor Web项目中&#xff0c;.razor 和 .cshtml 文件是常用的视图文件格式。尽管它们看起来有相似之处&#xff0c;但在使用方式、功能和渲染机制上有着根本的不同。理解它们的本质区别&#xff0c;有助于开发者更好地选择合适的文件格式&#xff0c;并构建符合需求的…...

SpringBoot快速使用

一些名词的碎碎念: 1> 俩种网络应用设计模式 C/S 客户端/服务器 B/S 浏览器/服务器 俩者对比: 2> 集群和分布式的概念 集群: 分布式: 例子: 一个公司有一个人身兼多职 集群: 招聘N个和上面这个人一样身兼多职 分布式: 招聘N个人,分担上面这个人的工作,进行工作的拆分. 工…...

【C语言实现:用队列模拟栈与用栈模拟队列(LeetCode 225 232)】

LeetCode刷题记录 &#x1f310; 我的博客主页&#xff1a;iiiiiankor&#x1f3af; 如果你觉得我的内容对你有帮助&#xff0c;不妨点个赞&#x1f44d;、留个评论✍&#xff0c;或者收藏⭐&#xff0c;让我们一起进步&#xff01;&#x1f4dd; 专栏系列&#xff1a;LeetCode…...

智慧医疗能源事业线深度画像分析(上)

引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...

聊聊 Pulsar:Producer 源码解析

一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台&#xff0c;以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中&#xff0c;Producer&#xff08;生产者&#xff09; 是连接客户端应用与消息队列的第一步。生产者…...

【第二十一章 SDIO接口(SDIO)】

第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全&#xff08;Thread Safety&#xff09; 线程安全是指在多线程环境下&#xff0c;某个函数、类或代码片段能够被多个线程同时调用时&#xff0c;仍能保证数据的一致性和逻辑的正确性&#xf…...

技术栈RabbitMq的介绍和使用

目录 1. 什么是消息队列&#xff1f;2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...

Mysql中select查询语句的执行过程

目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析&#xff08;Parser&#xff09; 2.4、执行sql 1. 预处理&#xff08;Preprocessor&#xff09; 2. 查询优化器&#xff08;Optimizer&#xff09; 3. 执行器…...

LangFlow技术架构分析

&#x1f527; LangFlow 的可视化技术栈 前端节点编辑器 底层框架&#xff1a;基于 &#xff08;一个现代化的 React 节点绘图库&#xff09; 功能&#xff1a; 拖拽式构建 LangGraph 状态机 实时连线定义节点依赖关系 可视化调试循环和分支逻辑 与 LangGraph 的深…...

通过MicroSip配置自己的freeswitch服务器进行调试记录

之前用docker安装的freeswitch的&#xff0c;启动是正常的&#xff0c; 但用下面的Microsip连接不上 主要原因有可能一下几个 1、通过下面命令可以看 [rootlocalhost default]# docker exec -it freeswitch fs_cli -x "sofia status profile internal"Name …...