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

[算法日志]图论刷题 沉岛思想的运用

[算法日志]图论刷题: 沉岛思想的运用

leetcode 695 岛屿最大面积

给你一个大小为 m x n 的二进制矩阵 grid .

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

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

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

本题依旧是一道较基础的图论搜索题,采用DFS, BFS 或者后面将要学的并查集都可以解决本题, 但本题的重点在于引入一种算法思想.

沉岛思想

本题我们将DFS作为本题基础. 但不同的是, 我们将不再使用visited数组作为访问过的标记, 转而代之的是我将直接再直接在grid数组上进行修改.

当我们访问过一个岛屿节点"1"时, 将其改为"0". 这种策略实际上与使用visited数组进行标记十分相似, 只不过没有额外分配一个数组, 转而在原本的数组上进行修改. 这其实是另一种算法思想(原地算法)的体现.

原地算法, 指在解决某种问题时,利用原本数据空间, 而不额外分配空间. 采用这种算法策略, 在面对较大数据量时, 可以有效节约内存空间, 降低空间复杂度.

以下是本题的示例代码:

	const int dir[4][2] = { {0, -1}, {1, 0}, {0, 1}, {-1, 0} };int DFS3(vector<vector<int>>& g, int x, int y){if (x < 0 || y < 0 || x >= g[0].size() || y >= g.size() || !g[y][x])return 0;int result = 1; g[y][x] = 0;for (int i = 0; i < 4; ++i)result += DFS3(g, x + dir[i][0], y + dir[i][1]);return result;}int  maxAreaOfIsland(vector<vector<int>>& grid) {if (grid.empty())return 0;int result = 0;for (int i = 0; i < grid.size(); ++i){for (int j = 0; j < grid[0].size(); ++j){if (grid[i][j]){result = max(result,DFS3(grid, j, i));}}}return result;}

当然, 在本题中, 我们写的是函数接口, 所以不推荐对原数据的修改, 但这种算法思想依旧值得我们学习与效仿.

相关文章:

[算法日志]图论刷题 沉岛思想的运用

[算法日志]图论刷题: 沉岛思想的运用 leetcode 695 岛屿最大面积 给你一个大小为 m x n 的二进制矩阵 grid . 岛屿 是由一些相邻的 1 (代表土地) 构成的组合, 这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻. 你可以假设 grid 的四个边缘都被 0&#xff08…...

Web服务器的搭建

网站需求&#xff1a; 1.基于域名www.openlab.com可以访问网站内容为 welcome to openlab!!! 2.给该公司创建三个网站目录分别显示学生信息&#xff0c;教学资料和缴费网站&#xff0c;基于www.openlab.com/student 网站访问学生信息&#xff0c;www.openlab.com/data网站访问教…...

如何使用 GTX750 或 1050 显卡安装 CUDA11+

前言 由于兼容性问题&#xff0c;使得我们若想用较新版本的 PyTorch&#xff0c;通过 GPU 方式训练模型&#xff0c;也得更换较新版本得 CUDA 工具包。然而 CUDA 的版本又与电脑显卡的驱动程序版本关联&#xff0c;如果是低版本的显卡驱动程序安装 CUDA11 及以上肯定会失败。 比…...

跟着森老师学React Hooks(1)——使用Vite构建React项目

Vite是一款构建工具&#xff0c;对ts有很好的支持&#xff0c;最近也是在前端越来越流行。 以往的React项目的初始化方式大多是通过脚手架create-react-app(本质是webpack)&#xff0c;其实比起Vite来构建&#xff0c;启动会慢一些。 所以这次跟着B站的一个教程&#xff0c;使用…...

强力解决使用node版本管理工具 NVM 出现的问题(找不到 node,或者找不到 npm)

强力解决使用node版本管理工具 NVM 出现的问题&#xff08;找不到 node&#xff0c;或者找不到 npm&#xff09; node与npm版本对应关系 nvm是好用的Nodejs版本管理工具&#xff0c; 通过它可以方便地在本地调换Node版本。 2020-05-28 Node当前长期稳定版12.17.0&#xff0c;…...

Docker指定容器使用内存

Docker指定容器使用内存 作者&#xff1a;铁乐与猫 如果是还没有生成的容器&#xff0c;你可以从指定镜像生成容器时特意加上 run -m 256m 或 --memory-swap512m来限制。 -m操作指定的是物理内存&#xff0c;还有虚拟交换分区默认也会生成同样的大小&#xff0c;而–memory-…...

做什么数据表格啊,要做就做数据可视化

是一堆数字更易懂&#xff0c;还是图表更易懂&#xff1f;很明显是图表&#xff0c;特别是数据可视化图表。数据可视化是一种将大量数据转化为视觉形式的过程&#xff0c;通过图形、图表、图像等方式呈现数据&#xff0c;以便更直观地理解和分析。 数据可视化更加生动、形象地…...

CSS特效003:太阳、地球、月球的旋转

GPT能够很好的应用到我们的代码开发中&#xff0c;能够提高开发速度。你可以利用其代码&#xff0c;做出一定的更改&#xff0c;然后实现效能。 css实战中&#xff0c;这种球体间的旋转&#xff0c;主要通过rotate()旋转函数来实现。实际上&#xff0c;蓝色的地球和黑色的月球…...

云计算的大模型之争,亚马逊云科技落后了?

文丨智能相对论 作者丨沈浪 “OpenAI使用了Azure的智能云服务”——在过去的半年&#xff0c;这几乎成为了微软智能云最好的广告词。 正所谓“水涨船高”&#xff0c;凭借OpenAI旗下的ChatGPT在全球范围内爆发&#xff0c;微软趁势拉了一波自家的云计算业务。2023年二季度&a…...

【form校验】3.0项目多层list嵌套

const { required, phoneOrMobile } CjmForm.rules; export default function detail() {const { query } getRouterInfo(location);const formRef useRef(null);const [crumbList, setCrumbList] useState([{url: "/wenling/Reviewer",name: "审核人员&quo…...

公共功能测试用例

1、UI测试 布局是否合理&#xff0c;输入框、按钮是否对齐 行列间距是否保持一致弹出窗口垂直居中对其界面的设计风格是否与UI的设计风格一致 系统是否使用统一风格的控件界面的文字是否简洁易懂&#xff0c;是否有错别字 兼容性测试&#xff1a;不同浏览器、版本、分辨率下&a…...

【电路笔记】-并联RLC电路分析

并联RLC电路分析 文章目录 并联RLC电路分析1、概述2、AC的行为3、替代配置3.1 带阻滤波器3.2 带通滤波器 4、总结 电子器件三个基本元件的串联行为已在我们之前的文章系列 RLC 电路分析中详细介绍。 在本文中&#xff0c;介绍了另一种称为并联 RLC 电路的关联。 在第一部分中&a…...

ros1 client

Client&#xff08;客户端&#xff09;&#xff1a;发布海龟生成请求 [类似Publisher] Serve&#xff08;服务端&#xff09;&#xff1a;海龟仿真器,接收请求 [类似于Subscriber] Service&#xff08;服务&#xff09;&#xff1a;生成海龟的具体内容&#xff0c;其中服务类型…...

射频功率放大器应用中GaN HEMT的表面电势模型

标题&#xff1a;A surface-potential based model for GaN HEMTs in RF power amplifier applications 来源&#xff1a;IEEE IEDM 2010 本文中的任何第一人称都为论文的直译 摘要&#xff1a;我们提出了第一个基于表面电位的射频GaN HEMTs紧凑模型&#xff0c;并将我们的工…...

CSP(Common Spatial Patterns)——EEG特征提取方法详解

基于CSP的运动想象 EEG 特征提取和可视化参考前文&#xff1a;https://blog.csdn.net/qq_43811536/article/details/134273470?spm1001.2014.3001.5501 目录 1. CSP是什么&#xff1f;1.1 CSP的含义1.2 CSP算法1.3 CSP特征的特点 2. CSP特征在EEG信号分类任务中的应用2.1 任务…...

【Git】Git 学习笔记_操作本地仓库

1. 安装与初始化配置 1.1 安装 下载地址 在文件夹里右键点击 git bash here 即可打开命令行面板。 git -v // 查看版本1.2 配置 git config --global user.name "heo" git config --global user.email xxxgmail.com git config --global credential.helper stor…...

杂记(3):在Pytorch中如何操作将数据集分为训练集和测试集?

在Pytorch中如何操作将数据集分为训练集和测试集&#xff1f; 0. 前言1. 手动切分2. train_test_split方法3. Pytorch自带方法4. 总结 0. 前言 数据集需要分为训练集和测试集&#xff01; 其中&#xff0c;训练集单纯用来训练&#xff0c;优化模型参数&#xff1b;测试集单纯用…...

【MySQL篇】数据库角色

前言 数据库角色是被命名的一组与数据库操作相关的权限&#xff0c;角色是权限的集合。因此&#xff0c;可以为一组具有相同权限的用户创建一个角色&#xff0c;使用角色来管理数据库权限可以简化授权的过程。 CREATE ROLE&#xff1a;创建一个角色 GRANT&#xff1a;给角色授…...

c++ 信奥赛编程 2050:【例5.20】字串包含

#include<iostream> #include<cstring> using namespace std; int main() {string str1,str2;int temp;cin>>str1>>str2;//判断长度 if(str1.size()<str2.size()){ swap(str1,str2); //交换内容 }str1str1str1; //AABCDAABCDAABCDAABCDif(str…...

用dbeaver创建一个enum类型,并讲述一部分,mysql的enum类型的知识

写这个博客的目的就是我在网上看了半天&#xff0c;发现没有这方面的知识&#xff0c;也许是老手认为这个太简单了&#xff0c;不过我还是告诉新人使用dbeaver来创建一个enum类型的方法&#xff1a; 就是enum("a","b","name") 第一步用dbeaver…...

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

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

Android Wi-Fi 连接失败日志分析

1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分&#xff1a; 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析&#xff1a; CTR…...

React Native 导航系统实战(React Navigation)

导航系统实战&#xff08;React Navigation&#xff09; React Navigation 是 React Native 应用中最常用的导航库之一&#xff0c;它提供了多种导航模式&#xff0c;如堆栈导航&#xff08;Stack Navigator&#xff09;、标签导航&#xff08;Tab Navigator&#xff09;和抽屉…...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍

文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结&#xff1a; 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析&#xff1a; 实际业务去理解体会统一注…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

Swagger和OpenApi的前世今生

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