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

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.岛屿的周长 分析&#xff1a; 1.陆地的旁边是海面&#xff0c;存在周长2.陆地在边界上&#xff0c;存在周长 思路一&#xff1a;深度优先遍历 1.通过记录访问情况来访问数据 class Solution { public:int direct[4][2]{{0,1},{0,-1},{1,0},{-1,0}};int res0;void dfs(…...

C++ - 完美语义(右值引用的中篇) - lambda表达式

前言 之前对右值引用的理解&#xff0c;用使用场景做了详细说明&#xff0c;具体看博客&#xff1a;C - 右值引用 和 移动拷贝-CSDN博客 在 有值引用 当中还有一个 完美转发&#xff0c;请看本篇博客。 完美转发 我们现在看这个例子&#xff1a; void Fun(int& x) { …...

常见排序算法详解

目录 排序的相关概念 排序&#xff1a; 稳定性&#xff1a; 内部排序&#xff1a; 外部排序&#xff1a; 常见的排序&#xff1a; 常见排序算法的实现 插入排序&#xff1a; 基本思想&#xff1a; 直…...

监控搭建-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、背景 随着项目信息化进程的推进&#xff0c;操作系统、…...

指纹浏览器开发指南-EasyBR

想开发一款指纹浏览器&#xff0c;指纹浏览器名字叫做EasyBR&#xff0c;大致构思了下开发的步骤。 EasyBR指纹浏览器开发指南&#xff1a; 后台技术、前端技术和指纹修改 简介&#xff1a; EasyBR指纹浏览器是一款旨在提供个性化服务和广告定位的浏览器&#xff0c;通过收…...

qml入门

window import QtQuick 2.15 import QtQuick.Window 2.15 import QtQuick.Controls 2.5Window { //root控件&#xff0c;父窗口是主界面width: 640height: 480visible: true//相对于父控件的偏移量x: 100y:100minimumWidth: 400 //最小宽度minimumHeight: 300 //最小高度ma…...

一文熟练使用python修改Excel中的数据

使用python修改Excel中的内容 1.初级修改 1.1 openpyxl库的功能&#xff1a; openpyxl模块是一个读写Excel 2010文档的Python库&#xff0c;如果要处理更早格式的Excel文档&#xff0c;需要用到额外的库&#xff0c;例如Xlwings。openpyxl是一个比较综合的工具&#xff0c;能…...

java Spring Boot在配置文件中关闭热部署

之前更大家一起搭建了一个热部署的开发环境 但是 大家要清楚一个情况 我们线上程序运行突然内部发生变化这是不可能的。 所以 他就只会对我们开发环境有效 是否开启 我们可以通过 application配置文件来完成 我这里是yml格式的 参考代码如下 spring:devtools:restart:enabled…...

【物联网】Arduino+ESP8266物联网开发(一):开发环境搭建 安装Arduino和驱动

ESP8266物联网开发 1.开发环境安装 开发软件下载地址&#xff1a; 链接: https://pan.baidu.com/s/1BaOY7kWTvh4Obobj64OHyA?pwd3qv8 提取码: 3qv8 1.1 安装驱动 将ESP8266连接到电脑上&#xff0c;安装ESP8266驱动CP210x 安装成功后&#xff0c;打开设备管理器&#xff0c…...

自定义UI对象转流程节点

自定义UI对象转流程节点 实体自定义对象转bpmn activitiy学习 (动态加签&#xff0c;动态流程图&#xff0c;指定节点跳转&#xff0c;指定多人节点跳转) 前端页面仿的这个 提供一个思路 实体 ActivitiValueVo import io.swagger.annotations.ApiModel; import io.swagger.a…...

P1-P5_动手学深度学习-pytorch(李沐版,粗浅的笔记)

目录 预告  1.学习深度学习的关键是动手  2.什么是《动手学深度学习》  3.曾经推出的版本&#xff08;含github链接&#xff09; 一、课程安排  1.目标  2.内容  3.上课形式  4.你将学到什么  5.资源 二、深度学习的介绍  1.AI地图  2.深度学习在一些应用上…...

Android Studio修改模拟器AVD Manger目录

Android Studio修改虚拟机AVD Manger目录 1、在AS的设备管理器Device Manager中删除原来创建的所有虚拟机&#xff08;Android Virtual Device&#xff09;&#xff1b; 2、新建一个自定义的AVD目录&#xff0c;例如&#xff1a;D:\Android\AndroidAVD 3、在高级系统设置中增加…...

STM32--MQ2烟雾传感器

本文主要介绍STM32F103C8T6和烟雾传感器模块的控制算法 简介 烟雾模块选用MQ-2气体传感器&#xff0c;根据传感器的电导率随空气中可燃气体浓度的增加而增大的特性检测空气中可燃气体&#xff0c;然后将电导率的变化转换成对应的电信号 MQ系列烟雾传感分类如下&#xff1a; 该…...

GitHub要求开启2FA,否则不让用了。

背景 其实大概在一个多月前&#xff0c;在 GitHub 网页端以及邮箱里都被提示&#xff1a;要求开启 2FA &#xff0c;即双因子认证&#xff1b;但是当时由于拖延症和侥幸心理作祟&#xff0c;直接忽略了相关信息&#xff0c;毕竟“又不是不能用”。。 只到今天发现 GitHub 直接…...

Python 编程基础 | 第三章-数据类型 | 3.6、元组

一、元组 Python 的元组与列表类似&#xff0c;不同之处在于元组的元素不能修改。元组使用小括号&#xff0c;列表使用方括号。 1、创建元组 元组创建很简单&#xff0c;只需要在括号中添加元素&#xff0c;并使用逗号隔开即可&#xff0c;例如&#xff1a; tup1 (physics, ch…...

2023/10/7 -- ARM

【程序状态寄存器读写指令】 1.指令码以及格式 mrs:读取CPSR寄存器的值 mrs 目标寄存器 CPSR&#xff1a;读取CPSR的数值保存到目标寄存器中msr:修改CPSR寄存器的数值msr CPSR,第一操作数:将第一操作数的数值保存到CPSR寄存器中//修改CPSR寄存器&#xff0c;也就表示程序的状…...

yolov5加关键点回归

文章目录 一、数据1&#xff09;数据准备2&#xff09;标注文件说明 二、基于yolov5-face 修改自己的yolov5加关键点回归1、dataloader,py2、augmentations.py3、loss.py4、yolo.py 一、数据 1&#xff09;数据准备 1、手动创建文件夹: yolov5-face-master/data/widerface/tr…...

untitle

实用的科研图形美化处理教程分享 ​ 显微照片排版标记 除了统计图表之外&#xff0c;显微照片也是文章中必不可少的实验结果呈现方式。除了常规实验的各种组织切片照片&#xff0c;在空间转录组文章中显微照片更是常见。显微照片的呈现方式也是有讲究的&#xff0c;比如对照片…...

《论文阅读》监督对抗性对比学习在对话中的情绪识别 ACL2023

《论文阅读》监督对抗性对比学习在对话中的情绪识别 前言摘要相关知识最坏样本干扰监督对比学习生成式对抗网络纳什均衡琴森香农散度范式球模型架构监督对抗性对比学习模型结构图实验结果问题前言 你是否也对于理解论文存在困惑? 你是否也像我之前搜索论文解读,得到只是中文…...

2023-10-07 LeetCode每日一题(股票价格跨度)

2023-10-07每日一题 一、题目编号 901. 股票价格跨度二、题目链接 点击跳转到题目位置 三、题目描述 设计一个算法收集某些股票的每日报价&#xff0c;并返回该股票当日价格的 跨度 。 当日股票价格的 跨度 被定义为股票价格小于或等于今天价格的最大连续日数&#xff08…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

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

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

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

QT3D学习笔记——圆台、圆锥

类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体&#xff08;对象或容器&#xff09;QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质&#xff08;定义颜色、反光等&#xff09;QFirstPersonC…...

20个超级好用的 CSS 动画库

分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码&#xff0c;而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库&#xff0c;可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画&#xff0c;可以包含在你的网页或应用项目中。 3.An…...

站群服务器的应用场景都有哪些?

站群服务器主要是为了多个网站的托管和管理所设计的&#xff0c;可以通过集中管理和高效资源的分配&#xff0c;来支持多个独立的网站同时运行&#xff0c;让每一个网站都可以分配到独立的IP地址&#xff0c;避免出现IP关联的风险&#xff0c;用户还可以通过控制面板进行管理功…...

(一)单例模式

一、前言 单例模式属于六大创建型模式,即在软件设计过程中,主要关注创建对象的结果,并不关心创建对象的过程及细节。创建型设计模式将类对象的实例化过程进行抽象化接口设计,从而隐藏了类对象的实例是如何被创建的,封装了软件系统使用的具体对象类型。 六大创建型模式包括…...

深入理解Optional:处理空指针异常

1. 使用Optional处理可能为空的集合 在Java开发中&#xff0c;集合判空是一个常见但容易出错的场景。传统方式虽然可行&#xff0c;但存在一些潜在问题&#xff1a; // 传统判空方式 if (!CollectionUtils.isEmpty(userInfoList)) {for (UserInfo userInfo : userInfoList) {…...