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.飞地的数量 分析:求不跟边界接壤的陆地的数量 思路一:深度优先遍历 先从四个侧边找陆地,然后进行深度优先遍历,把所有接壤的陆地(1)全部转换成海洋(0) 深度优先遍历…...
SpringBoot的全局异常拦截
在 Spring Boot 中,可以通过使用 ControllerAdvice 注解和 ExceptionHandler 注解来实现全局异常拦截。 RestControllerAdvice RestControllerAdvice 是 Spring Framework 提供的注解,用于定义全局异常处理类,并且结合 ExceptionHandler 注…...
『力扣每日一题11』:转换成小写字母
一、题目 给你一个字符串 s ,将该字符串中的大写字母转换成相同的小写字母,返回新的字符串。 示例 1: 输入:s "Hello" 输出:"hello"示例 2: 输入:s "here" 输…...
复习Day07:链表part03:21. 合并两个有序链表、2. 两数相加
之前的blog链接:https://blog.csdn.net/weixin_43303286/article/details/131700482?spm1001.2014.3001.5501 我用的方法是在leetcode再过一遍例题,明显会的就复制粘贴,之前没写出来就重写,然后从拓展题目中找题目来写。辅以Lab…...
Ubuntu中启动HDFS后没有NameNode解决办法
关闭进程: stop-dfs.sh 格式化: hadoop namenode -format 出现报错信息: 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包
参考文档: 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下载速度慢的方法很多,本文主要介绍通过Git镜像的方式解决下载慢的问题。 主要步骤有:1、找到gitconfig文件, 2、通过git命令查看当前生效的config 配置 3、使用git config命令编辑并添加国内镜像源 1、gitconfig 文件在…...
Redis与分布式-哨兵模式
接上文 Redis与分布式-主从复制 1.哨兵模式 启动一个哨兵,只需要修改配置文件即可, sentinel monitor lbwnb 1247.0.0.1 6001 1先将所有服务关闭,然后修改配置文件,redis Master,redis Slave,redis Slave…...
创建型设计模式 原型模式 建造者模式 创建者模式对比
创建型设计模式 单例 工厂模式 看这一篇就够了_软工菜鸡的博客-CSDN博客 4.3 原型模式 4.3.1 概述 用一个已经创建的实例作为原型,通过复制该原型对象来创建一个和原型对象相同的新对象。 4.3.2 结构 原型模式包含如下角色: 抽象原型类:规定了…...
HTML详细基础(二)文件路径
目录 一.相对路径 二.绝对路径 三.超链接标签 四.锚点链接 首先,扩展一些HTML执行的原理: htmL(hypertext markup Language) 是一种规范(或者说是一种标准),它通过标记符(tag)来标记要显示…...
大数据-玩转数据-Flink 海量数据实时去重
一、海量数据实时去重说明 借助redis的Set,需要频繁连接Redis,如果数据量过大, 对redis的内存也是一种压力;使用Flink的MapState,如果数据量过大, 状态后端最好选择 RocksDBStateBackend; 使用布隆过滤器,…...
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流程简述 输入分片: MapReduce 作业开始时,输入数据被分割成多个分片,每个分片大小一般在 16MB 到 128MB 之间。这些分片会被分配给不同的…...
C++中的四种强制类型转换符详解
前 言 C 既支持 C 风格的类型转换,又有自己风格的类型转换。C 风格的转换格式很简单,但是有不少缺点: 转换太过随意,可以在任意类型之间转换。你可以把一个指向 const 对象的指针转换成指向非 const 对象的指针,把一…...
Windows电脑多开器的优缺点对比
Windows电脑多开器是一种能够让用户同时运行多个应用程序、游戏或者网页的软件工具。它的作用在于让用户能够更加高效地工作、学习或者娱乐。但是,这种软件也存在一些优劣势的对比。 优点: 提升工作效率。多开器可以让用户同时打开多个应用程序或者网页…...
Java笔记六(面向对象:类与对象)
面向对象编程的本质:以类的方式组织代码,以对象的组织(封装)数据 抽象 三大特征:封装 继承 多态 从认识角度考虑是先有对象后有类。对象,是具体的事物。类,是抽象的,是对对象的抽…...
Git使用【中】
欢迎来到Cefler的博客😁 🕌博客主页:那个传说中的man的主页 🏠个人专栏:题目解析 🌎推荐文章:题目大解析3 目录 👉🏻分支管理分支概念git branch(查看/删除分…...
Greenplum7一键安装
2023年9月底,Greenplum 发布了7.0.0版本,并于2023年10月03日开放了安装部署说明文档,现在快速尝鲜版的docker一键部署方式如下: 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…...
观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...
华为云AI开发平台ModelArts
华为云ModelArts:重塑AI开发流程的“智能引擎”与“创新加速器”! 在人工智能浪潮席卷全球的2025年,企业拥抱AI的意愿空前高涨,但技术门槛高、流程复杂、资源投入巨大的现实,却让许多创新构想止步于实验室。数据科学家…...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...
调用支付宝接口响应40004 SYSTEM_ERROR问题排查
在对接支付宝API的时候,遇到了一些问题,记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...
Xshell远程连接Kali(默认 | 私钥)Note版
前言:xshell远程连接,私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...
相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了: 这一篇我们开始讲: 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下: 一、场景操作步骤 操作步…...
QMC5883L的驱动
简介 本篇文章的代码已经上传到了github上面,开源代码 作为一个电子罗盘模块,我们可以通过I2C从中获取偏航角yaw,相对于六轴陀螺仪的yaw,qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...
聊聊 Pulsar:Producer 源码解析
一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台,以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中,Producer(生产者) 是连接客户端应用与消息队列的第一步。生产者…...
基于当前项目通过npm包形式暴露公共组件
1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹,并新增内容 3.创建package文件夹...
iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈
在日常iOS开发过程中,性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期,开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发,但背后往往隐藏着系统资源调度不当…...
