LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法
文章目录
- 1 省份数量
- 题目描述
- 解题思路与代码
- 解法一:深度优先
- 解法二:广度优先
- 解法三:并查集
- 2 三角形的最大周长
- 题目描述
- 解题思路与代码
- 贪心算法:
1 省份数量
题目描述
有 n 个城市,其中一些彼此相连,另一些没有相连。如果城市 a 与城市 b 直接相连,且城市 b 与城市 c直接相连,那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市,组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ,其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连,而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中 省份 的数量。
解题思路与代码
解法一:深度优先
获取一个城市,通过递归找到离该城市最远的城市,标记为已访问,然后逐个向内进行标记
public int findCircleNum(int[][] isConnected) {int provinces = isConnected.length;boolean[] visited = new boolean[provinces];int circles = 0;for (int i = 0; i < provinces; i++) {if (!visited[i]) {dfs(isConnected, visited, provinces, i);circles++;}}return circles;}public void dfs(int[][] isConnected, boolean[] visited, int provinces, int i) {for (int j = 0; j < provinces; j++) {if (isConnected[i][j] == 1 && !visited[j]) {visited[j] = true;dfs(isConnected, visited, provinces, j);}}}
解法二:广度优先
获取一个城市,先标记与该城市直连的城市(最近的),然后逐步向外扩散寻找
public int bfs(int[][] isConnected) {int provinces = isConnected.length;boolean[] visited = new boolean[provinces];int circles = 0;Queue<Integer> queue = new LinkedList<Integer>();for (int i = 0; i < provinces; i++) {if (!visited[i]) {queue.offer(i);while (!queue.isEmpty()) {int j = queue.poll();visited[j] = true;for (int k = 0; k < provinces; k++) {if (isConnected[j][k] == 1 && !visited[k]) {queue.offer(k);}}}circles++;}}return circles;}
解法三:并查集
将每个城市看成一个节点,如果两个城市相连,则建立树关系,选出其中一个为head,如果两个树中的节点也相连,则将其中一个head设置为另一个树的head
两个方法 :一个寻找head节点,一个合并树
static int mergeFind(int[][] isConnected){int provinces = isConnected.length;int[] head = new int[provinces];int[] level = new int[provinces];for (int i = 0; i < provinces; i++) {head[i] = i;level[i] = 1;}for (int i = 0; i < provinces; i++) {for (int j = i + 1; j < provinces; j++) {if (isConnected[i][j] == 1) {merge(i, j,head,level);}}}int count = 0;//找出所有的headfor (int i = 0; i < provinces; i++) {if (head[i] == i) {count++;}}return count;}//查找head节点static int find(int x, int[] arr) {if(arr[x] == x)return x;elsearr[x] = find(arr[x],arr);//路径压缩,每一个节点直接能找到headreturn arr[x];}static void merge(int x, int y,int[] arr,int[] level) {int i = find(x,arr);int j = find(y,arr);//深度比较短的树的head往深度大的树上挂,使合并后的深度尽量小if(i == j){return;}if(level[i] <= level[j]){arr[i] = j;}else{arr[j] = i;}//深度加1level[j]++;}
2 三角形的最大周长
题目描述
给定由一些正数(代表长度)组成的数组 A ,返回由其中三个长度组成的、面积不为零的三角形的最大周长。
如果不能形成任何面积不为零的三角形,返回 0 。
解题思路与代码
贪心算法:
先小到大排序,假设最长边是最后下标,另外两条边是倒数第二和第三下标,则此时三角形周长最大
n < (n-1) + (n-2),如果不成立,意味着该数组中不可能有另外两个值之和大于n,此时将n左移,重新计算
public int largestPerimeter(int[] A) {Arrays.sort(A);for (int i = A.length - 1; i >= 2; --i) {if (A[i - 2] + A[i - 1] > A[i]) {return A[i - 2] + A[i - 1] + A[i];}}return 0;}
相关文章:
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目三角形最大周长java多种解法 文章目录1 省份数量题目描述解题思路与代码解法一:深度优先解法二:广度优先解法三:并查集2 三角形的最大周长题目描述解题思路与代码贪心算法:1…...

Vue3通透教程【一】Vue3现状—必然趋势?
文章目录🌟 专栏介绍🌟 Vue默认版本🌟 拥抱Vue3的UI🌟 Vue3显著优势🌟 小彩蛋🌟 写在最后🌟 专栏介绍 凉哥作为 Vue 的忠诚粉丝输出过大量的 Vue 文章,应粉丝要求开始更新 Vue3 的相…...

打破数据孤岛,Apache Doris 助力纵腾集团快速构建流批一体数仓架构|最佳实践
福建纵腾网络有限公司(简称“纵腾集团”)成立于 2009 年, 以“全球跨境电商基础设施服务商”为企业定位,聚焦跨境仓储与物流, 为全球跨境电商商户、出口贸易企业、出海品牌商提供海外仓储、商业专线物流、定制化物流等…...

什么是真正的骨传导耳机,骨传导耳机原理
骨传导耳机大多采用后挂耳/夹耳佩戴方式,但现在很多人分不清哪些是骨传导耳机,哪些是气传导耳机。看完这篇教会你辨别哪些是真正的骨传导耳机。 骨传导耳机采用固体传声方式,整个耳机机身都没有传声音孔的设计,主要通过耳机振子发…...

[MySQL]基本数据类型及表的基本操作
哈喽,大家好!我是保护小周ღ,本期为大家带来的是 MySQL 数据库常用的数据类型,数据表的基本操作:创建、删除、修改表,针对修改表的结构进行了讲解,随后是如何向数据表中添加数据,浅浅…...
华为OD机试 - 好朋友(Python) | 机试题+算法思路+考点+代码解析 【2023】
好朋友 题目 在学校中 N个小朋友站成一队 第i个小朋友的身高为height[i] 第i个小朋友可以看到第一个比自己身高更高的小朋友j 那么j是i的好朋友 (要求:j > i) 请重新生成一个列表 对应位置的输出是每个小朋友的好朋友的位置 如果没有看到好朋友 请在该位置用0代替 小朋友…...
SAP ABAP用程序给用户增加SAP_ALL权限
给用户增加SAP_ALL的权限,报表可对basis与abap开发人员对用户权限管理的思路,谢绝用于其它用途,后果自负。 REPORT ZTESTCREATEUSER. data: l_USR04 LIKE USR04 , l_UST04 LIKE UST04 , l_PROFS LIKE USR04-PROFS , l_…...

stm32f407探索者开发板(二十)——独立看门狗实验
文章目录一、独立看门狗概述1.1 独立看门狗二、常用寄存器和库函数配置2.1 独立看门狗框图2.2 键值寄存器IWDG_KR2.3 预分频寄存器IWDG_PR2.4 重装载寄存器IWDG_RLR2.5 状态寄存器IWDG_SR2.6 IWDG独立看门狗操作库函数三、手写独立看门狗实验3.1 操作步骤3.2 iwdg.c3.3 iwdg.h3…...

C语言进阶(五)—— 多维数组
1. 一维数组 元素类型角度:数组是相同类型的变量的有序集合内存角度:连续的一大片内存空间在讨论多维数组之前,我们还需要学习很多关于一维数组的知识。首先让我们学习一个概念。1.1 数组名考虑下面这些声明:int a; int b[10];我们…...

06_MySQL多表查询
多表查询,也称为关联查询,指两个或更多个表一起完成查询操作。前提条件:这些一起查询的表之间是有关系的(一对一、一对多),它们之间一定是有关联字段,这个关联字段可能建立了外键,也…...

程序员赚钱指南,兼职社区招募
👨💻作者简介:大数据专业硕士在读,CSDN人工智能领域博客专家,阿里云专家博主,专注大数据与人工智能知识分享。 🎉专栏推荐:目前在写一个CV方向专栏,后期会更新不限于目…...

Qt-FFmpeg开发-实现录屏功能(10)
#音视频/FFmpeg #Qt Qt-FFmpeg开发-实现录屏功能💬 文章目录Qt-FFmpeg开发-实现录屏功能💬1、概述💥2、实现效果💨3、FFmpeg录屏代码流程👁️🗨️4、主要代码🤙5、完整源代码🤏更…...

JavaEE简单示例——动态SQL元素<where>
简单介绍: 在我们之前使用where关键字进行查询的时候,总是会在后面添加一个11恒等式,并且在每一个可能拼接的SQL语句前面都加上一个and关键字,防止当后续的所有条件都不满足的时候,where关键字在最后直接跟and的时候也…...

本地事务详解
1、事务的基本性质 数据库事务的几个特性:原子性(Atomicity )、一致性( Consistency )、隔离性或独立性( Isolation) 和持久性(Durabilily),简称就是 ACID; 原子性:一系列的操作整体不可拆分,要么同时成功&#x…...

e2e测试-Cypress 使用
● 官网 ● GitHub 一、安装 # npm npm install cypress --save-dev# yarn yarn add cypress --dev添加 npm 脚本: {"scripts": {"cypress:open": "cypress open"} }启动: npm run cypress:open二、编写测试 Cypress…...

20230222 【梳理】肿瘤检测 预处理+ML+DL
一、预处理 1、形态学【使图像中的重要部分更加可见,并消除MRI图像的琐碎部分。】 形态学操作是一种非线性操作,涉及在二值图像上移动一个窗口(或结构元素),以一种方式帮助增长图像(膨胀)或缩小图像(侵蚀)[30]。这种预处理技术更有用,特别是当MRI图像中存在不需要...

经典文献阅读之--MSC-VO(曼哈顿和结构约束VIO)
0. 简介 对于视觉里程计而言,在面对低纹理场景时,往往会出现退化的问题,究其原因是人造环境往往很难找到足够数量的点特征。而其他的几何视觉线索则是比较容易找到,在城市等场景中,通常表现出结构规律,如平…...
华为OD机试真题Python实现【字母计数】真题+解题思路+代码(20222023
字母计数 题目 给出一个只包含字母的字符串, 不包含空格,统计字符串中各个子字母(区分大小写)出现的次数, 并按照字母出现次数从大到小的顺序输出各个字母及其出现次数 如果次数相同,按照自然顺序排序,且小写字母在大写字母之前 🔥🔥🔥🔥🔥👉👉👉👉👉�…...

在中国市场,假如Teradata像Nutanix那样“退出操作”,谁来“接盘”呢?
【引言】:看它的选择,是数据仓库发展必然还是偶然呢?【全球存储观察 | 热点关注】前些天,将逐步结束在中国市场直接运营的Teradata引发了业界大量关注与讨论。作为全球数据仓库领域的绝对领导者,为什么会退…...

使用vs2022编译yolov5+tensorRT+cuda+cudnn代码进行混合编译
首先依赖有cuda、cudnn、tensorrt、protobuf,从Linux的代码直接移植过来这些库是没法使用的,需要下载对应win的下的版本,其中cuda、cudnn和tensorrt直接从官方下载即可,但是protobuf需要自己编译一下(protobuf3.11.4&a…...

Docker 离线安装指南
参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性,不同版本的Docker对内核版本有不同要求。例如,Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本,Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...
设计模式和设计原则回顾
设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以? 在 Golang 的面试中,map 类型的使用是一个常见的考点,其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...
IGP(Interior Gateway Protocol,内部网关协议)
IGP(Interior Gateway Protocol,内部网关协议) 是一种用于在一个自治系统(AS)内部传递路由信息的路由协议,主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...
c++ 面试题(1)-----深度优先搜索(DFS)实现
操作系统:ubuntu22.04 IDE:Visual Studio Code 编程语言:C11 题目描述 地上有一个 m 行 n 列的方格,从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子,但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...
AI编程--插件对比分析:CodeRider、GitHub Copilot及其他
AI编程插件对比分析:CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展,AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者,分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

C# 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖
在Vuzix M400 AR智能眼镜的助力下,卢森堡罗伯特舒曼医院(the Robert Schuman Hospitals, HRS)凭借在无菌制剂生产流程中引入增强现实技术(AR)创新项目,荣获了2024年6月7日由卢森堡医院药剂师协会࿰…...

[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.
ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #:…...

[ACTF2020 新生赛]Include 1(php://filter伪协议)
题目 做法 启动靶机,点进去 点进去 查看URL,有 ?fileflag.php说明存在文件包含,原理是php://filter 协议 当它与包含函数结合时,php://filter流会被当作php文件执行。 用php://filter加编码,能让PHP把文件内容…...