day-65 代码随想录算法训练营(19)图论 part 04
463.岛屿的周长
分析:
- 1.陆地的旁边是海面,存在周长
- 2.陆地在边界上,存在周长
思路一:深度优先遍历
- 1.通过记录访问情况来访问数据
class Solution {
public:int direct[4][2]={{0,1},{0,-1},{1,0},{-1,0}};int res=0;void dfs(vector<vector<int>>&grid,vector<vector<bool>>&visted,int x,int y){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(!visted[nextx][nexty]){if(grid[nextx][nexty]==0) res++;//那一边是海面else{visted[nextx][nexty]=true;dfs(grid,visted,nextx,nexty);}}}else res++;//那一边是边界}}int islandPerimeter(vector<vector<int>>& grid) {int n=grid.size(),m=grid[0].size();vector<vector<bool>>visted(n,vector<bool>(m,false));for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(!visted[i][j] && grid[i][j]==1){visted[i][j]=true;dfs(grid,visted,i,j);}}}return res;}
};
1971.寻找图中是否存在路径
分析:
- 寻找两个节点间是否存在路径,就是寻找两个节点是否在同一集合中
思路一:并查集
- 1.初始化集合
- 2.把各个节点进行连接
- 3.寻根判断
class Solution {
public:int n=200005;vector<int>father=vector<int>(n,0);void init(){//并查集初始化for(int i=0;i<n;i++) father[i]=i;}int find(int u){//并查集寻根return u==father[u]?u:father[u]=find(father[u]);}bool isSame(int u,int v){u=find(u);v=find(v);return u==v;}void join(int u,int v){//连接两个节点u=find(u);v=find(v);if(u==v) return;//说明已经存在连接father[u]=v;//进行连接}bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {init();for(int i=0;i<edges.size();i++) join(edges[i][0],edges[i][1]);//连接节点return isSame(source,destination);//寻根判断}
};
684.冗余连接
分析:
- 1.出现两个节点在同一集合,即有冗余
思路一:并查集
- 1.初始化
- 2.边添加边判断
class Solution {
public:vector<int>father=vector<int>(1001,0);void init(){for(int i=0;i<1001;i++) father[i]=i;}int find(int u){//寻根return u==father[u]?u:father[u]=find(father[u]);}bool isSame(int u,int v){//判断是否同一集合u=find(u);v=find(v);if(u==0 && v==0) return false;return u==v;}void join(int u,int v){//连接节点u=find(u);v=find(v);if(u==v) return;father[u]=v;}vector<int> findRedundantConnection(vector<vector<int>>& edges) {init();//初始化!!!int n=edges.size();for(int i=0;i<n;i++){if(isSame(edges[i][0],edges[i][1])) return edges[i];//出现两个节点在同一集合else join(edges[i][0],edges[i][1]);}return vector<int>();}
};
685.冗余连接 ||
分析:
- 只存在一条冗余边,有三种情况:

- 1.入度可以通过遍历获取
- 2.环可以通过判断两节点是否在同一集合获取
思路一:并查集
- 1.先获取所有节点的入度
- 2.存在节点入度为2:
- 倒序找出入度为 2 的节点边
- 节点边不考虑时,判断图是否为树
- 3.不存在节点入度为2:
- 判断删除那一条边存在环,直接返回
class Solution {
public:static const int N=1010;int father[N];int n;void init(){//初始化for(int i=1;i<=n;++i) father[i]=i;}int find(int u){//寻根return u==father[u]?u:father[u]=find(father[u]);}bool same(int u,int v){//判断是否在同一集合u=find(u);v=find(v);return u==v;}void join(int u,int v){//连接两个节点u=find(u);v=find(v);if(u==v) return;father[u]=v;}vector<int> getMoveEdge(const vector<vector<int>>&edges){//获取要删除的冗余边init();for(int i=0;i<n;i++){if(same(edges[i][0],edges[i][1])) return edges[i];//已经存在同一集合,所以此线冗余join(edges[i][0],edges[i][1]);}return {};//不存在冗余}bool judge(const vector<vector<int>>&edges,int deleteEdge){//判断删除该边是否是树init();for(int i=0;i<n;i++){if(i==deleteEdge) continue;//删除就不考虑if(same(edges[i][0],edges[i][1])) return false;//仍然存在同一集合,绝对不是树join(edges[i][0],edges[i][1]);}return true;}vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {n=edges.size();int inDegree[N]={0};vector<int>mid;for(int i=0;i<n;i++) inDegree[edges[i][1]]++;//记录入度for(int i=n-1;i>=0;i--){//从右侧开始记录if(inDegree[edges[i][1]]==2) mid.push_back(i);//记录入度为2的节点的下标}if(mid.size()>0){//存在入度为2的节点if(judge(edges,mid[0])) return edges[mid[0]];//最右边的边不考虑,图为树else return edges[mid[1]];}return getMoveEdge(edges);}
};
相关文章:
day-65 代码随想录算法训练营(19)图论 part 04
463.岛屿的周长 分析: 1.陆地的旁边是海面,存在周长2.陆地在边界上,存在周长 思路一:深度优先遍历 1.通过记录访问情况来访问数据 class Solution { public:int direct[4][2]{{0,1},{0,-1},{1,0},{-1,0}};int res0;void dfs(…...
C++ - 完美语义(右值引用的中篇) - lambda表达式
前言 之前对右值引用的理解,用使用场景做了详细说明,具体看博客:C - 右值引用 和 移动拷贝-CSDN博客 在 有值引用 当中还有一个 完美转发,请看本篇博客。 完美转发 我们现在看这个例子: void Fun(int& x) { …...
常见排序算法详解
目录 排序的相关概念 排序: 稳定性: 内部排序: 外部排序: 常见的排序: 常见排序算法的实现 插入排序: 基本思想: 直…...
监控搭建-Prometheus
监控搭建-Prometheus 1、背景2、目标3、选型4、Prometheus4.1、介绍4.2、架构4.3、构件4.4、运行机制4.5、环境介绍4.6、数据准备4.7、网络策略4.7.1、主机端口放行4.7.2、设备端口放行 4.8、部署4.9、验证4.10、配置 1、背景 随着项目信息化进程的推进,操作系统、…...
指纹浏览器开发指南-EasyBR
想开发一款指纹浏览器,指纹浏览器名字叫做EasyBR,大致构思了下开发的步骤。 EasyBR指纹浏览器开发指南: 后台技术、前端技术和指纹修改 简介: EasyBR指纹浏览器是一款旨在提供个性化服务和广告定位的浏览器,通过收…...
qml入门
window import QtQuick 2.15 import QtQuick.Window 2.15 import QtQuick.Controls 2.5Window { //root控件,父窗口是主界面width: 640height: 480visible: true//相对于父控件的偏移量x: 100y:100minimumWidth: 400 //最小宽度minimumHeight: 300 //最小高度ma…...
一文熟练使用python修改Excel中的数据
使用python修改Excel中的内容 1.初级修改 1.1 openpyxl库的功能: openpyxl模块是一个读写Excel 2010文档的Python库,如果要处理更早格式的Excel文档,需要用到额外的库,例如Xlwings。openpyxl是一个比较综合的工具,能…...
java Spring Boot在配置文件中关闭热部署
之前更大家一起搭建了一个热部署的开发环境 但是 大家要清楚一个情况 我们线上程序运行突然内部发生变化这是不可能的。 所以 他就只会对我们开发环境有效 是否开启 我们可以通过 application配置文件来完成 我这里是yml格式的 参考代码如下 spring:devtools:restart:enabled…...
【物联网】Arduino+ESP8266物联网开发(一):开发环境搭建 安装Arduino和驱动
ESP8266物联网开发 1.开发环境安装 开发软件下载地址: 链接: https://pan.baidu.com/s/1BaOY7kWTvh4Obobj64OHyA?pwd3qv8 提取码: 3qv8 1.1 安装驱动 将ESP8266连接到电脑上,安装ESP8266驱动CP210x 安装成功后,打开设备管理器,…...
自定义UI对象转流程节点
自定义UI对象转流程节点 实体自定义对象转bpmn activitiy学习 (动态加签,动态流程图,指定节点跳转,指定多人节点跳转) 前端页面仿的这个 提供一个思路 实体 ActivitiValueVo import io.swagger.annotations.ApiModel; import io.swagger.a…...
P1-P5_动手学深度学习-pytorch(李沐版,粗浅的笔记)
目录 预告 1.学习深度学习的关键是动手 2.什么是《动手学深度学习》 3.曾经推出的版本(含github链接) 一、课程安排 1.目标 2.内容 3.上课形式 4.你将学到什么 5.资源 二、深度学习的介绍 1.AI地图 2.深度学习在一些应用上…...
Android Studio修改模拟器AVD Manger目录
Android Studio修改虚拟机AVD Manger目录 1、在AS的设备管理器Device Manager中删除原来创建的所有虚拟机(Android Virtual Device); 2、新建一个自定义的AVD目录,例如:D:\Android\AndroidAVD 3、在高级系统设置中增加…...
STM32--MQ2烟雾传感器
本文主要介绍STM32F103C8T6和烟雾传感器模块的控制算法 简介 烟雾模块选用MQ-2气体传感器,根据传感器的电导率随空气中可燃气体浓度的增加而增大的特性检测空气中可燃气体,然后将电导率的变化转换成对应的电信号 MQ系列烟雾传感分类如下: 该…...
GitHub要求开启2FA,否则不让用了。
背景 其实大概在一个多月前,在 GitHub 网页端以及邮箱里都被提示:要求开启 2FA ,即双因子认证;但是当时由于拖延症和侥幸心理作祟,直接忽略了相关信息,毕竟“又不是不能用”。。 只到今天发现 GitHub 直接…...
Python 编程基础 | 第三章-数据类型 | 3.6、元组
一、元组 Python 的元组与列表类似,不同之处在于元组的元素不能修改。元组使用小括号,列表使用方括号。 1、创建元组 元组创建很简单,只需要在括号中添加元素,并使用逗号隔开即可,例如: tup1 (physics, ch…...
2023/10/7 -- ARM
【程序状态寄存器读写指令】 1.指令码以及格式 mrs:读取CPSR寄存器的值 mrs 目标寄存器 CPSR:读取CPSR的数值保存到目标寄存器中msr:修改CPSR寄存器的数值msr CPSR,第一操作数:将第一操作数的数值保存到CPSR寄存器中//修改CPSR寄存器,也就表示程序的状…...
yolov5加关键点回归
文章目录 一、数据1)数据准备2)标注文件说明 二、基于yolov5-face 修改自己的yolov5加关键点回归1、dataloader,py2、augmentations.py3、loss.py4、yolo.py 一、数据 1)数据准备 1、手动创建文件夹: yolov5-face-master/data/widerface/tr…...
untitle
实用的科研图形美化处理教程分享 显微照片排版标记 除了统计图表之外,显微照片也是文章中必不可少的实验结果呈现方式。除了常规实验的各种组织切片照片,在空间转录组文章中显微照片更是常见。显微照片的呈现方式也是有讲究的,比如对照片…...
《论文阅读》监督对抗性对比学习在对话中的情绪识别 ACL2023
《论文阅读》监督对抗性对比学习在对话中的情绪识别 前言摘要相关知识最坏样本干扰监督对比学习生成式对抗网络纳什均衡琴森香农散度范式球模型架构监督对抗性对比学习模型结构图实验结果问题前言 你是否也对于理解论文存在困惑? 你是否也像我之前搜索论文解读,得到只是中文…...
2023-10-07 LeetCode每日一题(股票价格跨度)
2023-10-07每日一题 一、题目编号 901. 股票价格跨度二、题目链接 点击跳转到题目位置 三、题目描述 设计一个算法收集某些股票的每日报价,并返回该股票当日价格的 跨度 。 当日股票价格的 跨度 被定义为股票价格小于或等于今天价格的最大连续日数(…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...
HTML 语义化
目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案: 语义化标签: <header>:页头<nav>:导航<main>:主要内容<article>&#x…...
论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)
笔记整理:刘治强,浙江大学硕士生,研究方向为知识图谱表示学习,大语言模型 论文链接:http://arxiv.org/abs/2407.16127 发表会议:ISWC 2024 1. 动机 传统的知识图谱补全(KGC)模型通过…...
UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)
UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中,UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化…...
稳定币的深度剖析与展望
一、引言 在当今数字化浪潮席卷全球的时代,加密货币作为一种新兴的金融现象,正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而,加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下,稳定…...
Linux 中如何提取压缩文件 ?
Linux 是一种流行的开源操作系统,它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间,使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的,要在 …...
uniapp手机号一键登录保姆级教程(包含前端和后端)
目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号(第三种)后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...
Webpack性能优化:构建速度与体积优化策略
一、构建速度优化 1、升级Webpack和Node.js 优化效果:Webpack 4比Webpack 3构建时间降低60%-98%。原因: V8引擎优化(for of替代forEach、Map/Set替代Object)。默认使用更快的md4哈希算法。AST直接从Loa…...
解决:Android studio 编译后报错\app\src\main\cpp\CMakeLists.txt‘ to exist
现象: android studio报错: [CXX1409] D:\GitLab\xxxxx\app.cxx\Debug\3f3w4y1i\arm64-v8a\android_gradle_build.json : expected buildFiles file ‘D:\GitLab\xxxxx\app\src\main\cpp\CMakeLists.txt’ to exist 解决: 不要动CMakeLists.…...
日常一水C
多态 言简意赅:就是一个对象面对同一事件时做出的不同反应 而之前的继承中说过,当子类和父类的函数名相同时,会隐藏父类的同名函数转而调用子类的同名函数,如果要调用父类的同名函数,那么就需要对父类进行引用&#…...
