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

day-63 代码随想录算法训练营(19) 图论 part 02

1020.飞地的数量

分析:求不跟边界接壤的陆地的数量
思路一:深度优先遍历
  • 先从四个侧边找陆地,然后进行深度优先遍历,把所有接壤的陆地(1)全部转换成海洋(0)
    • 深度优先遍历:从四个方向进行递归遍历
  • 遍历整个图,统计所有陆地的数量。
class Solution {
public:int direct[4][2]={{0,1},{0,-1},{1,0},{-1,0}};int res=0;void dfs(vector<vector<int>>&grid,int x,int y){grid[x][y]=0;for(int i=0;i<4;i++){int nextx=x+direct[i][0];int nexty=y+direct[i][1];if(nextx>=0 && nextx<grid.size() && nexty>=0 && nexty<grid[0].size()){//边界条件if(grid[nextx][nexty]==1){grid[nextx][nexty]=0;dfs(grid,nextx,nexty);}}}}int numEnclaves(vector<vector<int>>& grid) {int n=grid.size(),m=grid[0].size();for(int i=0;i<n;i++){if(grid[i][0]==1) dfs(grid,i,0);//左侧边if(grid[i][m-1]==1) dfs(grid,i,m-1);//右侧边}for(int j=0;j<m;j++){if(grid[0][j]==1) dfs(grid,0,j);//上侧边if(grid[n-1][j]==1) dfs(grid,n-1,j);//下侧边}for(int i=1;i<n-1;i++){//遍历整个图for(int j=1;j<m-1;j++){if(grid[i][j]==1) res++;}}return res;}
};

130.被围绕的区域

思路一:dfs
  • 依然是从四个侧面把陆地深度优先遍历,然后改成 A 字符
  • 然后遍历整个图,把剩余的陆地(必然被海水包裹)变为海水,A 字符变为陆地
class Solution {
public:int direct[4][2]={{0,1},{0,-1},{1,0},{-1,0}};int res=0;void dfs(vector<vector<char>>&board,char target,int x,int y){board[x][y]=target;res++;for(int i=0;i<4;i++){int nextx=x+direct[i][0];int nexty=y+direct[i][1];if(nextx>=0 && nextx<board.size() && nexty>=0 && nexty<board[0].size()){if(board[nextx][nexty]=='O'){board[nextx][nexty]=target;dfs(board,target,nextx,nexty);}}}}void solve(vector<vector<char>>& board) {int n=board.size(),m=board[0].size();for(int i=0;i<n;i++){if(board[i][0]=='O') dfs(board,'A',i,0);//左侧边if(board[i][m-1]=='O') dfs(board,'A',i,m-1);//右侧边}for(int j=0;j<m;j++){if(board[0][j]=='O') dfs(board,'A',0,j);//上侧边if(board[n-1][j]=='O') dfs(board,'A',n-1,j);//下侧边}for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(board[i][j]=='A') board[i][j]='O';//所有的A变为Oelse if(board[i][j]=='O') board[i][j]='X';//所有的O变为X}} }
};

417.太平洋大西洋流水问题

思路一:深度优先遍历
  • 分别从大西洋和太平洋一侧,倒着推得到两个数组
  • 当两个数组都经过同一位置时,说明可以流向两边
class Solution {
public:int direct[4][2]={{1,0},{-1,0},{0,1},{0,-1}};void dfs(vector<vector<int>>&heights,vector<vector<bool>>&visted,int x,int y){if(visted[x][y]) return;visted[x][y]=true;for(int i=0;i<4;i++){int nextx=x+direct[i][0];int nexty=y+direct[i][1];if(nextx>=0 && nextx<heights.size() && nexty>=0 && nexty<heights[0].size()){if(heights[x][y]<=heights[nextx][nexty])//本来是从高到低,这是倒着推,所以低到高dfs(heights,visted,nextx,nexty);}}}vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {int n=heights.size(),m=heights[0].size();vector<vector<int>>res;vector<vector<bool>>pacific(n,vector<bool>(m,false));//太平洋vector<vector<bool>>atlantic(n,vector<bool>(m,false));//大西洋for(int i=0;i<n;i++){dfs(heights,pacific,i,0);//从左侧太平洋出发dfs(heights,atlantic,i,m-1);//从右侧大西洋出发}for(int j=0;j<m;j++){dfs(heights,pacific,0,j);//从上侧太平洋出发dfs(heights,atlantic,n-1,j);//从下侧大西洋出发}for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(pacific[i][j] && atlantic[i][j])//从大西洋和太平洋都可以流过res.push_back({i,j});}}return res;}
};

相关文章:

day-63 代码随想录算法训练营(19) 图论 part 02

1020.飞地的数量 分析&#xff1a;求不跟边界接壤的陆地的数量 思路一&#xff1a;深度优先遍历 先从四个侧边找陆地&#xff0c;然后进行深度优先遍历&#xff0c;把所有接壤的陆地&#xff08;1&#xff09;全部转换成海洋&#xff08;0&#xff09; 深度优先遍历&#xf…...

SpringBoot的全局异常拦截

在 Spring Boot 中&#xff0c;可以通过使用 ControllerAdvice 注解和 ExceptionHandler 注解来实现全局异常拦截。 RestControllerAdvice RestControllerAdvice 是 Spring Framework 提供的注解&#xff0c;用于定义全局异常处理类&#xff0c;并且结合 ExceptionHandler 注…...

『力扣每日一题11』:转换成小写字母

一、题目 给你一个字符串 s &#xff0c;将该字符串中的大写字母转换成相同的小写字母&#xff0c;返回新的字符串。 示例 1&#xff1a; 输入&#xff1a;s "Hello" 输出&#xff1a;"hello"示例 2&#xff1a; 输入&#xff1a;s "here" 输…...

复习Day07:链表part03:21. 合并两个有序链表、2. 两数相加

之前的blog链接&#xff1a;https://blog.csdn.net/weixin_43303286/article/details/131700482?spm1001.2014.3001.5501 我用的方法是在leetcode再过一遍例题&#xff0c;明显会的就复制粘贴&#xff0c;之前没写出来就重写&#xff0c;然后从拓展题目中找题目来写。辅以Lab…...

Ubuntu中启动HDFS后没有NameNode解决办法

关闭进程&#xff1a; stop-dfs.sh 格式化&#xff1a; hadoop namenode -format 出现报错信息&#xff1a; 23/10/03 22:27:04 WARN fs.FileUtil: Failed to delete file or dir [/usr/data/hadoop/tmp/dfs/name/current/fsimage_0000000000000000000.md5]: it still exi…...

AWS-Lambda之导入自定义包-pip包

参考文档&#xff1a; https://repost.aws/zh-Hans/knowledge-center/lambda-import-module-error-python https://blog.csdn.net/fxtxz2/article/details/112035627 简单来说,以 " alibabacloud_dyvmsapi20170525 " 包为例 ## 创建临时目录 mkdir /tmp cd ./tmp …...

MAC 如何解决GitHub下载速度慢的问题

说在前面 解决github下载速度慢的方法很多&#xff0c;本文主要介绍通过Git镜像的方式解决下载慢的问题。 主要步骤有&#xff1a;1、找到gitconfig文件&#xff0c; 2、通过git命令查看当前生效的config 配置 3、使用git config命令编辑并添加国内镜像源 1、gitconfig 文件在…...

Redis与分布式-哨兵模式

接上文 Redis与分布式-主从复制 1.哨兵模式 启动一个哨兵&#xff0c;只需要修改配置文件即可&#xff0c; sentinel monitor lbwnb 1247.0.0.1 6001 1先将所有服务关闭&#xff0c;然后修改配置文件&#xff0c;redis Master&#xff0c;redis Slave&#xff0c;redis Slave…...

创建型设计模式 原型模式 建造者模式 创建者模式对比

创建型设计模式 单例 工厂模式 看这一篇就够了_软工菜鸡的博客-CSDN博客 4.3 原型模式 4.3.1 概述 用一个已经创建的实例作为原型&#xff0c;通过复制该原型对象来创建一个和原型对象相同的新对象。 4.3.2 结构 原型模式包含如下角色&#xff1a; 抽象原型类&#xff1a;规定了…...

HTML详细基础(二)文件路径

目录 一.相对路径 二.绝对路径 三.超链接标签 四.锚点链接 首先&#xff0c;扩展一些HTML执行的原理&#xff1a; htmL(hypertext markup Language) 是一种规范&#xff08;或者说是一种标准&#xff09;&#xff0c;它通过标记符&#xff08;tag&#xff09;来标记要显示…...

大数据-玩转数据-Flink 海量数据实时去重

一、海量数据实时去重说明 借助redis的Set&#xff0c;需要频繁连接Redis&#xff0c;如果数据量过大, 对redis的内存也是一种压力&#xff1b;使用Flink的MapState&#xff0c;如果数据量过大, 状态后端最好选择 RocksDBStateBackend&#xff1b; 使用布隆过滤器&#xff0c;…...

1.在vsCode上创建Hello,World

(1).编译器的安装配置 使用vsCode进行编写c语言,首先需要安装gcc编译器,可以自己去寻找资料或者gcc官网进行下载. 下载好后,将文件夹放入到自己指定的目录后,配置系统环境变量,将path指向编译器的bin目录 进入bin目录打开cmd,输入gcc -v,然后就会成功输出信息. (2).vsCode配…...

XrayGLM - 医学大模型

文章目录 关于 XrayGLM研究背景VisualGLM-6B 关于 XrayGLM XrayGLM: 首个会看胸部X光片的中文多模态医学大模型 | The first Chinese Medical Multimodal Model that Chest Radiographs Summarization. 基于VisualGLM-6B 微调 github : https://github.com/WangRongsheng/Xra…...

Hive 常见数据倾斜场景及解决方案(Map\Join\Reduce端)

目录 MapReduce流程简述a) Map倾斜b) Join倾斜c) Reduce倾斜 首先回顾一下MapReduce的流程 MapReduce流程简述 输入分片&#xff1a; MapReduce 作业开始时&#xff0c;输入数据被分割成多个分片&#xff0c;每个分片大小一般在 16MB 到 128MB 之间。这些分片会被分配给不同的…...

C++中的四种强制类型转换符详解

前 言 C 既支持 C 风格的类型转换&#xff0c;又有自己风格的类型转换。C 风格的转换格式很简单&#xff0c;但是有不少缺点&#xff1a; 转换太过随意&#xff0c;可以在任意类型之间转换。你可以把一个指向 const 对象的指针转换成指向非 const 对象的指针&#xff0c;把一…...

Windows电脑多开器的优缺点对比

Windows电脑多开器是一种能够让用户同时运行多个应用程序、游戏或者网页的软件工具。它的作用在于让用户能够更加高效地工作、学习或者娱乐。但是&#xff0c;这种软件也存在一些优劣势的对比。 优点&#xff1a; 提升工作效率。多开器可以让用户同时打开多个应用程序或者网页…...

Java笔记六(面向对象:类与对象)

面向对象编程的本质&#xff1a;以类的方式组织代码&#xff0c;以对象的组织&#xff08;封装&#xff09;数据 抽象 三大特征&#xff1a;封装 继承 多态 从认识角度考虑是先有对象后有类。对象&#xff0c;是具体的事物。类&#xff0c;是抽象的&#xff0c;是对对象的抽…...

Git使用【中】

欢迎来到Cefler的博客&#x1f601; &#x1f54c;博客主页&#xff1a;那个传说中的man的主页 &#x1f3e0;个人专栏&#xff1a;题目解析 &#x1f30e;推荐文章&#xff1a;题目大解析3 目录 &#x1f449;&#x1f3fb;分支管理分支概念git branch&#xff08;查看/删除分…...

Greenplum7一键安装

2023年9月底&#xff0c;Greenplum 发布了7.0.0版本&#xff0c;并于2023年10月03日开放了安装部署说明文档&#xff0c;现在快速尝鲜版的docker一键部署方式如下&#xff1a; mkdir /data/gpdb docker run -d --name greenplum -p 15432:5432 -v /data/gpdb:/data inrgihc/g…...

Springboo整合Sentinel

Springboo整合Sentinel 1.启动Sentinel java -jar sentinel-dashboard-1.8.6.jar2.访问localhost:8080到Sentinel管理界面(默认账号和密码都是sentinel) 3.引入依赖(注意版本对应) <dependency><groupId>com.alibaba.cloud</groupId><artifactId>spr…...

conda相比python好处

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

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

在建筑行业&#xff0c;项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升&#xff0c;传统的管理模式已经难以满足现代工程的需求。过去&#xff0c;许多企业依赖手工记录、口头沟通和分散的信息管理&#xff0c;导致效率低下、成本失控、风险频发。例如&#…...

【大模型RAG】Docker 一键部署 Milvus 完整攻略

本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装&#xff1b;只需暴露 19530&#xff08;gRPC&#xff09;与 9091&#xff08;HTTP/WebUI&#xff09;两个端口&#xff0c;即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...

基础测试工具使用经验

背景 vtune&#xff0c;perf, nsight system等基础测试工具&#xff0c;都是用过的&#xff0c;但是没有记录&#xff0c;都逐渐忘了。所以写这篇博客总结记录一下&#xff0c;只要以后发现新的用法&#xff0c;就记得来编辑补充一下 perf 比较基础的用法&#xff1a; 先改这…...

linux 错误码总结

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

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序

一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...

C++八股 —— 单例模式

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

USB Over IP专用硬件的5个特点

USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中&#xff0c;从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备&#xff08;如专用硬件设备&#xff09;&#xff0c;从而消除了直接物理连接的需要。USB over IP的…...

【Go语言基础【12】】指针:声明、取地址、解引用

文章目录 零、概述&#xff1a;指针 vs. 引用&#xff08;类比其他语言&#xff09;一、指针基础概念二、指针声明与初始化三、指针操作符1. &&#xff1a;取地址&#xff08;拿到内存地址&#xff09;2. *&#xff1a;解引用&#xff08;拿到值&#xff09; 四、空指针&am…...

Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)

引言 在人工智能飞速发展的今天&#xff0c;大语言模型&#xff08;Large Language Models, LLMs&#xff09;已成为技术领域的焦点。从智能写作到代码生成&#xff0c;LLM 的应用场景不断扩展&#xff0c;深刻改变了我们的工作和生活方式。然而&#xff0c;理解这些模型的内部…...