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

算法|图论 2

LeetCode 695- 岛屿的最大面积

题目链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

题目描述:给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿 是由一些相邻的 1 (代表土地) 构成的组合,这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0(代表水)包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿,则返回面积为 0 。

解题思路

思路一(深度优先遍历):

  1. 首先确定递归函数的参数,返回值。本题要路径,我们直接设置两个全局变量res和tmp,这样可以不用写太多参数传递。返回值就是void,参数需要图和一个x和y来记录当前在哪个岛屿。下次从这个岛屿开始走的。
  2. 确定终止条件,本题按我们的逻辑,先进入循环再判断是否应该终止,那么终止条件就是:当超出网格范围 或 该岛屿已经是海洋 就终止。
  3. 单层处理逻辑,每次将当前岛屿淹没,并且让这片岛屿的面积++(因为我们是确定了当前是陆地才会进入下层递归)。
class Solution {
public:
int res = 0;//记录最大面积
int tmp = 0;//当前这片岛屿的面积int maxAreaOfIsland(vector<vector<int>>& grid) {for (int i = 0; i < grid.size(); i++) {for (int j = 0; j < grid[0].size(); j++) {if (grid[i][j] == 1) {dfs(grid, i, j);//当这次递归结束的时候,说明这片岛屿已经全部被淹没了,此时我们可以记录一下//这片岛屿的面积,并将tmp置为0,也就是下一片岛屿从新计算大小res = max(res,tmp);tmp = 0;}}}return res;}
public:void dfs(vector<vector<int>>& grid, int i, int j) {if (i < 0 || j < 0  || i >= grid.size() || j >= grid[0].size() ||  grid[i][j] != 1){return;}grid[i][j] = 0;//当前如果是陆地那么就让岛屿大小++tmp++;dfs(grid, i + 1, j);dfs(grid, i - 1, j);dfs(grid, i, j + 1);dfs(grid, i, j - 1);}
};

思路二(广度优先遍历):

与之前一题一样,就是多一个计算每片岛屿面积的tmp

class Solution {
public:int res = 0;int tmp = 0;int dir[4][2] = {0,1,1,0,-1,0,0,-1};int maxAreaOfIsland(vector<vector<int>>& grid) {for(int i=0;i<grid.size();i++){for(int j=0;j<grid[0].size();j++){if(grid[i][j] == 1){bfs(grid,i,j);res = max(res,tmp);tmp = 0;}}}return res;}void bfs(vector<vector<int>> &grid,int x,int y){queue<pair<int,int>> que;que.push({x,y});grid[x][y] = 0;tmp++;//这里也要面积++,因为第一次进入也淹没了一个小岛屿。while(!que.empty()){pair<int,int> cur = que.front();que.pop();int curx = cur.first;int cury = cur.second;for(int i=0;i<4;i++){int nextx = curx + dir[i][0];int nexty = cury + dir[i][1];if(nextx < 0 || nexty < 0 || nextx >= grid.size() || nexty >= grid[0].size() ||grid[nextx][nexty] != 1) continue;que.push({nextx,nexty});grid[nextx][nexty] = 0;tmp++;}}}
};

总结:

  • 深搜和广搜的问题,这题的广搜需要注意,只要淹没就得加面积的。

LeetCode 1020- 飞地的数量

题目链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

题目描述:给你一个大小为 m x n 的二进制矩阵 grid ,其中 0 表示一个海洋单元格、1 表示一个陆地单元格。一次 移动 是指从一个陆地单元格走到另一个相邻(上、下、左、右)的陆地单元格或跨过 grid 的边界。

返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。

解题思路

思路一(深度优先遍历):

  1. 首先确定递归函数的参数,返回值。本题不需要这些。不过这题我们要设置一个全局变量cango表示是否能走到界外。为false不能走到界外,为true则可以走到界外。
  2. 确定终止条件,本题按我们的逻辑,先进入循环再判断是否应该终止,那么终止条件就是:当超出网格范围 当前遍历的是海洋 就终止。不过这里需要注意,这道题目需要求的是不能走到界外的岛屿的数量。所以终止条件处理的时候有些区别。当出界的时候就将cango设置为true表示可以走出界并返回。当遇到的是海洋,就直接返回。
  1. 单层处理逻辑,每次我们将当前岛屿的值设置为0,模拟为被淹没,并且去淹没当前节点的上下左右相邻的节点。为1的节点为陆地状态,并且将tmp++,表示相连的岛屿数量加一。在每次递归完出来的时候,说明走完了这一片岛屿,我们可以看看是否能走出界,不能则将tmp 加到res中,并且将tmp置为0(cango不做操作,因为默认不能走出去)。可以则将cango置为false,并且将tmp置为0。直到这片海域没有岛屿为止。
class Solution {
public:int res = 0;int tmp = 0;bool cango = false;//标记当前这片岛屿能否走到界外void dfs(vector<vector<int>> &grid,int x,int y){//若到达界外,则标记为true,返回if(x < 0 || y < 0 || x >= grid.size() || y >= grid[0].size()){cango = true;return ;}//若是海洋,也返回if(grid[x][y] == 0) return;//将岛屿淹没grid[x][y] = 0;//这片岛屿数量加一tmp ++;dfs(grid,x+1,y);dfs(grid,x-1,y);dfs(grid,x,y+1);dfs(grid,x,y-1);}int numEnclaves(vector<vector<int>>& grid) {int m = grid.size(),n = grid[0].size();for(int i=0;i<m;i++){for(int j=0;j<n;j++){//若遇到岛屿,则进行深度优先遍历if(grid[i][j] == 1){dfs(grid,i,j);//若标记为不能走到边界,则将tmp加到结果中if(cango == false){res += tmp;//将tmp清零tmp = 0;}else{//若无法走到边界,则将cango改为默认值falsetmp = 0;cango = false;}}}}return res;}
};

思路二(广度优先遍历):

就是多了一个不能走出界则将岛屿数加到结果中的操作。

class Solution {
public:int tmp = 0;int res = 0;bool cango = false;//标记是否能走到界外int dir[4][2] = {0,1,1,0,-1,0,0,-1};void bfs(vector<vector<int>> &grid,int x,int y){queue<pair<int,int>> que;//存储对组的队列,存坐标用的que.push({x,y});//压入当前的坐标grid[x][y] = 0;//淹没当前岛屿tmp ++;//只要有淹没,就tmp++while(!que.empty()){pair<int,int> cur = que.front();//取出队头元素que.pop();//弹出队头for(int i=0;i<4;i++){//遍历四个方向,看是否有岛屿int nextx = cur.first + dir[i][0];int nexty = cur.second + dir[i][1];if(nextx < 0 || nexty < 0 || nextx >= grid.size() || nexty >= grid[0].size()){cango = true;continue;}if(0 == grid[nextx][nexty]) continue;tmp++;que.push({nextx,nexty});grid[nextx][nexty] = 0;}}}int numEnclaves(vector<vector<int>>& grid) {int m = grid.size(),n = grid[0].size();for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j] == 1){bfs(grid,i,j);if(false == cango){res += tmp;}else{cango = false;}tmp = 0;}}}return res;}
};

总结:

  • 多了一个加岛屿的操作。

相关文章:

算法|图论 2

LeetCode 695- 岛屿的最大面积 题目链接&#xff1a;力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 题目描述&#xff1a;给你一个大小为 m x n 的二进制矩阵 grid 。 岛屿 是由一些相邻的 1 (代表土地) 构成的组合&#xff0c;这里的「相邻」要求…...

使用C#实现服务端与客户端的简陋聊天

服务端代码: using System; using System.Net.Sockets; using System.Net; using System.IO;//服务器程序 namespace CSharpStudy_09_21 {class Program{static void Main(string[] args){int port 8865;TcpClient tcpClient;//创建tcp对象IPAddress[] serverIp Dns.GetHost…...

生成式模型和判别式模型区别

目录 1.概念 2.定义​ 3.举例​ &#xff08;1&#xff09;例子 A​ &#xff08;2&#xff09;例子 B​ 4.特点 5.优缺点 6.代表算法 1.概念 首先我们需要明确&#xff0c;两种不同的模型都用于监督学习任务中。监督学习的任务就是从数据中学习一个模型&#xff0c;并用…...

【kafka实战】03 SpringBoot使用kafka生产者和消费者示例

本节主要介绍用SpringBoot进行开发时&#xff0c;使用kafka进行生产和消费 一、引入依赖 <dependencies><dependency><groupId>org.springframework.kafka</groupId><artifactId>spring-kafka</artifactId></dependency><depen…...

Only file and data URLs are supported by the default ESM loader

1.版本问题 说明&#xff1a;将node版本提高就可以了。 2.nvm 说明&#xff1a;如果不想重复安装node版本&#xff0c;那么可以参考本人的nvm文档. nvm版本控制工具_FOREVER-Q的博客-CSDN博客...

LeetCode01

LeetCode01 两数之和 给定一个整数数组 nums 和一个整数目标值 target&#xff0c;请你在该数组中找出 和 为目标值 target 的那两个整数&#xff0c;并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是&#xff0c;数组中同一个元素在答案里不能重复出现。 你…...

计算机网络高频面试题集锦

问题1&#xff1a;谈一谈对OSI七层模型和TCP/IP四层模型的理解&#xff1f; 回答点&#xff1a;七层模型每层对应的作用及相关协议、为什么分层、为什么有TCP/IP四层模型 参考&#xff1a; 1、OSI七层参考模型是一个ISO组织所提出的一个标准参考分层模型&#xff0c;它按照数…...

Linux启动过程详解 Xmind导图笔记

参考大佬博客&#xff1a; 简要描述linux系统从开机到登陆界面的启动过程 Linux启动过程详解 Bootloader详解 来源&#xff1a;从BIOS开始画图了解Linux启动过程——老杨Linux...

Qt5开发及实例V2.0-第十七章-Qt版MyWord字处理软件

Qt5开发及实例V2.0-第十七章-Qt版MyWord字处理软件 第17章-Qt版MyWord字处理软件17.1 运行界面17.1.1 菜单设计基本操作17.1.2.MyWord系统菜单 17.2 工具栏设计17.2.1 与菜单对应的工具条17.2.2 附加功能的工具条 这段代码的作用是加载系统标准字号集&#xff0c;只要在主窗体构…...

机器视觉工程师们,常回家看看

我们在这个社会上扮演着多重角色&#xff0c;有时候我们很难平衡好这些角色之间的关系。 人们常言&#xff0c;积善成德&#xff0c;改变命运。善修者&#xff0c;懂得积累&#xff0c;懂得改变命运的重要性。 我曾年少不知父母之不易。一路依靠&#xff0c;一路成长。 所谓…...

网络隔离下实现的文件传输,现有的方式真的安全吗?

在当今的信息化时代&#xff0c;网络安全已经成为了各个企业和机构不可忽视的问题。为了保护内部数据和系统不受外部网络的攻击和泄露&#xff0c;一些涉及国家安全、商业机密、个人隐私等敏感信息的企业和机构&#xff0c;通常会对内外网进行隔离&#xff0c;即建立一个独立的…...

[医学图像知识]CT图和PET图的成像表现形式

1.CT图通常来说是单通道灰色图&#xff0c;用灰度值表示了结构对于x射线的吸收程度。 2.PET/SPECT图最初也是灰度图&#xff0c;用灰度值表示细胞的反射gama射线的程度&#xff0c;但是为了更好的观测不同细胞等的区别&#xff0c;通常将灰度图转化为了 伪彩色图像。 找个例子…...

聊聊wireshark的进阶使用功能 | 京东云技术团队

1. 前言 emmm&#xff0c;说起网络知识学习肯定离不来wireshark工具&#xff0c;这个工具能够帮助我们快速地定位网络问题以及帮助正在学习网络协议这块的知识的同学验证理论与实际的一大利器&#xff0c;平时更多的只是停留在初步的使用阶段。也是利用部门内部的网络兴趣小组…...

小米手机安装面具教程(Xiaomi手机获取root权限)

文章目录 1.Magisk中文网&#xff1a;2.某呼&#xff1a;3.最后一步打开cmd命令行输入的时候:4.Flash Boot 通包-Magisk&#xff08;Flash Boot通刷包&#xff09;5.小米Rom下载&#xff08;官方刷机包&#xff09;6.Magisk最新版本国内源下载 1.Magisk中文网&#xff1a; htt…...

DSU ON TREE

DSU ON TREE DSU&#xff1a;并查集 DSU ON TREE&#xff1a;树上启发式合并 我也不知道为啥树上并查集就是树上启发式合并 启发式合并的思想是每次把小的往大的合并&#xff0c;也就是最大化利用已有的答案&#xff08;大的数组不用清空&#xff0c;在原基础上加上小的即可&…...

Java“对象”

Java&#xff1a;PO、VO、BO、DO、DAO、DTO、POJO PO持久化对象&#xff08;Persistent Object&#xff09; PO是持久化对象&#xff0c;用于表示数据库中的实体或表的映射通常与数据库表的结构和字段对应PO的属性对应数据库表的字段&#xff0c;可以进行持久化操作&#xff0…...

vuepress+gitee免费搭建个人在线博客(无保留版)

文章目录 最终效果&#xff0c;一睹为快&#xff01;一、工具选型二、什么是VuePress三、准备工作3.1 node 安装3.2 Git安装3.3 Gitee账号注册 四、搭建步骤4.1 初始化VuePress4.2 安装VuePress4.3 初始化目录4.4 编写文章 五、部署到Gitee5.1 创建仓库5.2 个人空间地址设置4.3…...

Android 12.0 系统限制上网系列之iptables用IOemNetd实现app上网白名单的功能实现

1.前言 在12.0的系统rom定制化开发中,对于系统限制网络的使用,在system中netd网络这块的产品需要中,会要求设置app上网白名单的功能, liunx中iptables命令也是比较重要的,接下来就来在IOemNetd这块实现app上网白名单的的相关功能,就是在 系统中只能允许某个app上网,就是…...

Idea和DataGrip自定义常用代码模板,熟练使用快捷模板可促进开发效率

场景&#xff1a; 在实际工作中&#xff0c;我们不可能一个一个字母的去敲代码&#xff0c;为了提升开发效率&#xff0c;可以使用常用的快捷代码模板。idea和datagrip自带的有&#xff0c;我们也可以自定义快捷模板 一、Idea自定义代码模板、有些是基于 hutool 常用包 1、-&g…...

Vue.js :实现嵌套对话框的查看按钮

Vue.js &#xff1a;实现嵌套对话框的查看按钮 Vue.js 是一款流行的 JavaScript 框架&#xff0c;用于构建交互性强、响应式的前端应用程序。本博客将介绍如何使用 Vue.js 和 Element UI 库创建一个前端应用&#xff0c;其中包括了嵌套对话框的查看按钮&#xff0c;以及如何在…...

conda相比python好处

Conda 作为 Python 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

06 Deep learning神经网络编程基础 激活函数 --吴恩达

深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

代码随想录刷题day30

1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币&#xff0c;另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额&#xff0c;返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...