当前位置: 首页 > 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…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

三体问题详解

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

JDK 17 新特性

#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持&#xff0c;不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的&#xff…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

JS设计模式(4):观察者模式

JS设计模式(4):观察者模式 一、引入 在开发中&#xff0c;我们经常会遇到这样的场景&#xff1a;一个对象的状态变化需要自动通知其他对象&#xff0c;比如&#xff1a; 电商平台中&#xff0c;商品库存变化时需要通知所有订阅该商品的用户&#xff1b;新闻网站中&#xff0…...

沙箱虚拟化技术虚拟机容器之间的关系详解

问题 沙箱、虚拟化、容器三者分开一一介绍的话我知道他们各自都是什么东西&#xff0c;但是如果把三者放在一起&#xff0c;它们之间到底什么关系&#xff1f;又有什么联系呢&#xff1f;我不是很明白&#xff01;&#xff01;&#xff01; 就比如说&#xff1a; 沙箱&#…...

Python学习(8) ----- Python的类与对象

Python 中的类&#xff08;Class&#xff09;与对象&#xff08;Object&#xff09;是面向对象编程&#xff08;OOP&#xff09;的核心。我们可以通过“类是模板&#xff0c;对象是实例”来理解它们的关系。 &#x1f9f1; 一句话理解&#xff1a; 类就像“图纸”&#xff0c;对…...

C++ 类基础:封装、继承、多态与多线程模板实现

前言 C 是一门强大的面向对象编程语言&#xff0c;而类&#xff08;Class&#xff09;作为其核心特性之一&#xff0c;是理解和使用 C 的关键。本文将深入探讨 C 类的基本特性&#xff0c;包括封装、继承和多态&#xff0c;同时讨论类中的权限控制&#xff0c;并展示如何使用类…...

CSS 工具对比:UnoCSS vs Tailwind CSS,谁是你的菜?

在现代前端开发中&#xff0c;Utility-First (功能优先) CSS 框架已经成为主流。其中&#xff0c;Tailwind CSS 无疑是市场的领导者和标杆。然而&#xff0c;一个名为 UnoCSS 的新星正以其惊人的性能和极致的灵活性迅速崛起。 这篇文章将深入探讨这两款工具的核心理念、技术差…...