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

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经典算法题&#xff1a;矩阵中省份数量经典题目三角形最大周长java多种解法 文章目录1 省份数量题目描述解题思路与代码解法一&#xff1a;深度优先解法二&#xff1a;广度优先解法三&#xff1a;并查集2 三角形的最大周长题目描述解题思路与代码贪心算法&#xff1a;1…...

Vue3通透教程【一】Vue3现状—必然趋势?

文章目录&#x1f31f; 专栏介绍&#x1f31f; Vue默认版本&#x1f31f; 拥抱Vue3的UI&#x1f31f; Vue3显著优势&#x1f31f; 小彩蛋&#x1f31f; 写在最后&#x1f31f; 专栏介绍 凉哥作为 Vue 的忠诚粉丝输出过大量的 Vue 文章&#xff0c;应粉丝要求开始更新 Vue3 的相…...

打破数据孤岛,Apache Doris 助力纵腾集团快速构建流批一体数仓架构|最佳实践

福建纵腾网络有限公司&#xff08;简称“纵腾集团”&#xff09;成立于 2009 年&#xff0c; 以“全球跨境电商基础设施服务商”为企业定位&#xff0c;聚焦跨境仓储与物流&#xff0c; 为全球跨境电商商户、出口贸易企业、出海品牌商提供海外仓储、商业专线物流、定制化物流等…...

什么是真正的骨传导耳机,骨传导耳机原理

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

[MySQL]基本数据类型及表的基本操作

哈喽&#xff0c;大家好&#xff01;我是保护小周ღ&#xff0c;本期为大家带来的是 MySQL 数据库常用的数据类型&#xff0c;数据表的基本操作&#xff1a;创建、删除、修改表&#xff0c;针对修改表的结构进行了讲解&#xff0c;随后是如何向数据表中添加数据&#xff0c;浅浅…...

华为OD机试 - 好朋友(Python) | 机试题+算法思路+考点+代码解析 【2023】

好朋友 题目 在学校中 N个小朋友站成一队 第i个小朋友的身高为height[i] 第i个小朋友可以看到第一个比自己身高更高的小朋友j 那么j是i的好朋友 (要求:j > i) 请重新生成一个列表 对应位置的输出是每个小朋友的好朋友的位置 如果没有看到好朋友 请在该位置用0代替 小朋友…...

SAP ABAP用程序给用户增加SAP_ALL权限

给用户增加SAP_ALL的权限&#xff0c;报表可对basis与abap开发人员对用户权限管理的思路&#xff0c;谢绝用于其它用途&#xff0c;后果自负。 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. 一维数组 元素类型角度&#xff1a;数组是相同类型的变量的有序集合内存角度&#xff1a;连续的一大片内存空间在讨论多维数组之前&#xff0c;我们还需要学习很多关于一维数组的知识。首先让我们学习一个概念。1.1 数组名考虑下面这些声明&#xff1a;int a; int b[10];我们…...

06_MySQL多表查询

多表查询&#xff0c;也称为关联查询&#xff0c;指两个或更多个表一起完成查询操作。前提条件&#xff1a;这些一起查询的表之间是有关系的&#xff08;一对一、一对多&#xff09;&#xff0c;它们之间一定是有关联字段&#xff0c;这个关联字段可能建立了外键&#xff0c;也…...

程序员赚钱指南,兼职社区招募

&#x1f468;‍&#x1f4bb;作者简介&#xff1a;大数据专业硕士在读&#xff0c;CSDN人工智能领域博客专家&#xff0c;阿里云专家博主&#xff0c;专注大数据与人工智能知识分享。 &#x1f389;专栏推荐&#xff1a;目前在写一个CV方向专栏&#xff0c;后期会更新不限于目…...

Qt-FFmpeg开发-实现录屏功能(10)

#音视频/FFmpeg #Qt Qt-FFmpeg开发-实现录屏功能&#x1f4ac; 文章目录Qt-FFmpeg开发-实现录屏功能&#x1f4ac;1、概述&#x1f4a5;2、实现效果&#x1f4a8;3、FFmpeg录屏代码流程&#x1f441;️‍&#x1f5e8;️4、主要代码&#x1f919;5、完整源代码&#x1f90f;更…...

JavaEE简单示例——动态SQL元素<where>

简单介绍&#xff1a; 在我们之前使用where关键字进行查询的时候&#xff0c;总是会在后面添加一个11恒等式&#xff0c;并且在每一个可能拼接的SQL语句前面都加上一个and关键字&#xff0c;防止当后续的所有条件都不满足的时候&#xff0c;where关键字在最后直接跟and的时候也…...

本地事务详解

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

e2e测试-Cypress 使用

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

20230222 【梳理】肿瘤检测 预处理+ML+DL

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

经典文献阅读之--MSC-VO(曼哈顿和结构约束VIO)

0. 简介 对于视觉里程计而言&#xff0c;在面对低纹理场景时&#xff0c;往往会出现退化的问题&#xff0c;究其原因是人造环境往往很难找到足够数量的点特征。而其他的几何视觉线索则是比较容易找到&#xff0c;在城市等场景中&#xff0c;通常表现出结构规律&#xff0c;如平…...

华为OD机试真题Python实现【字母计数】真题+解题思路+代码(20222023

字母计数 题目 给出一个只包含字母的字符串, 不包含空格,统计字符串中各个子字母(区分大小写)出现的次数, 并按照字母出现次数从大到小的顺序输出各个字母及其出现次数 如果次数相同,按照自然顺序排序,且小写字母在大写字母之前 🔥🔥🔥🔥🔥👉👉👉👉👉�…...

在中国市场,假如Teradata像Nutanix那样“退出操作”,谁来“接盘”呢?

【引言】&#xff1a;看它的选择&#xff0c;是数据仓库发展必然还是偶然呢&#xff1f;【全球存储观察 &#xff5c; 热点关注】前些天&#xff0c;将逐步结束在中国市场直接运营的Teradata引发了业界大量关注与讨论。作为全球数据仓库领域的绝对领导者&#xff0c;为什么会退…...

使用vs2022编译yolov5+tensorRT+cuda+cudnn代码进行混合编译

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

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

C# 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

[大语言模型]在个人电脑上部署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 #&#xff1a…...

[ACTF2020 新生赛]Include 1(php://filter伪协议)

题目 做法 启动靶机&#xff0c;点进去 点进去 查看URL&#xff0c;有 ?fileflag.php说明存在文件包含&#xff0c;原理是php://filter 协议 当它与包含函数结合时&#xff0c;php://filter流会被当作php文件执行。 用php://filter加编码&#xff0c;能让PHP把文件内容…...