当前位置: 首页 > 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…...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

Java 语言特性(面试系列1)

一、面向对象编程 1. 封装&#xff08;Encapsulation&#xff09; 定义&#xff1a;将数据&#xff08;属性&#xff09;和操作数据的方法绑定在一起&#xff0c;通过访问控制符&#xff08;private、protected、public&#xff09;隐藏内部实现细节。示例&#xff1a; public …...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...