力扣:611. 有效三角形的个数

2023-10-14 00:36

本文主要是介绍力扣:611. 有效三角形的个数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

今日为大家分享一道力扣611有效三角形的个数!本文将会为大家为大家讲解题目,然后算法思路,最后再进行代码的实现!希望看完本文能对读者有一定的收获!


一、题目描述

通过题目的描述可以看出,意思是给定一个数组,然后观察数组中能元素组成三角形的个数!

题目上面那个例题可以看出,不同位置相同的数组也算不同的情况!


二、算法解析+代码!

相信不少小伙伴一看到本题,想到的大多都是暴力法!即:依次遍历,然后统计每次的数据是否能组成三角形!这样的解法是没毛病,但是放在力扣里面,其时间复杂度是很大可能是通不过的!下面我就来为大家写一下这种暴力枚举的算法代码!(在进行暴力枚举之前,可以将数组排成有序的!方便我们后边的暴力枚举分情况!)


1.暴力枚举

class Solution {
public://首先先将数组中的元素进行排序,可以有效的减少时间的复杂度!//然后根据单调性,利用双指针来判断能否组成三角形!int triangleNumber(vector<int>& nums){ sort(nums.begin(),nums.end());//暴力枚举!int count=0;int len=nums.size();for(int i=0;i<len-2;i++){for(int j=i+1;j<len-1;j++){for(int k=j+1;k<len;k++){if(nums[i]+nums[j]>nums[k]){   count++;}}}}return count;}
};

果然不出我们所料,暴力枚举的时间复杂度过高!直接不能通过!那么我们能否再想出一种更优的算法呢!当然可以,我们可以根据数组的单调性,然后进行双指针思路进行求解!

2.双指针思路

双指针思路,是基于在有序的前提下!在讲述双指针的前提下!我们首先补充一点数学的知识!

组成三角形的条件:大家都知道组成三角形的条件是任意两边之和大于第三边即可组成三角形,显然这需要比较三次!那么能否只比较一次来判断是否能组成三角形呢

答案是肯定的,如果两个较小的边相加大于最大的那个边就可以组成三角形,此时只需要比较一次即可!

双指针思路大致分为以下两步:

1.依次选取最大值(max)!

2.然后定义左右指针,根据左右指针的值的和(sum)与最大值比较是否可以组成三角形!

第二步又细分为两种情况!

2.1 当sum的值大于max,可以组成三角形!又因为是数组元素是单调的,所以left后面的数值与right的数值相加都可以组成三角形!即有right-left种情况!再让right--继续进行判断!

2.2当sum的值小于等于max时,不能组成三角形,只需要让left++再次进行判断即可求解!(最后当左右指针相遇时本次循环结束!)


图解:


代码如下:

class Solution {
public://首先先将数组中的元素进行排序,可以有效的减少时间的复杂度!//然后根据单调性,利用双指针来判断能否组成三角形!int triangleNumber(vector<int>& nums){int len = nums.size() - 1;//数学知识:组成三角形的条件:两个较小的边相加大于最大边才能组成三角形!sort(nums.begin(), nums.end());//排过序后,依次选取最大值,然后对最大值左边的区间进行双指针判断!//最大值左边的区间进行判断能否组成三角形!//1.sum >max    可以组成三角形! 既然能够组成三角形 进行right-left统计组数!//2.sum <=max  left++,当大于max时,统计个数即可!int count = 0;for (int i = len; i >= 2; i--){int max = nums[i];int left = 0;int right = i - 1;while (left < right){if (nums[left] + nums[right] > max){count += (right - left);right--;}else{left++;}}}return count;}
};

通过双指针算法,本例题顺利的通过了!

至此,本道题目讲解结束,希望能对读者有一定的收获,也希望能留下各位看官免费的小心心哦!

这篇关于力扣:611. 有效三角形的个数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/206915

相关文章

一文教你PyCharm如何有效地添加源与库

《一文教你PyCharm如何有效地添加源与库》在使用PyCharm进行Python开发的时候,很多时候我们需要添加库或者设置源,下面我们就来和大家详细介绍一下如何在PyCharm中添加源和库吧... 在使用PyCharm进行python开发的时候,很多时候我们需要添加库或者设置源。这些操作可以帮助我们更方便

OpenManus本地部署实战亲测有效完全免费(最新推荐)

《OpenManus本地部署实战亲测有效完全免费(最新推荐)》文章介绍了如何在本地部署OpenManus大语言模型,包括环境搭建、LLM编程接口配置和测试步骤,本文给大家讲解的非常详细,感兴趣的朋友一... 目录1.概况2.环境搭建2.1安装miniconda或者anaconda2.2 LLM编程接口配置2

Linux虚拟机不显示IP地址的解决方法(亲测有效)

《Linux虚拟机不显示IP地址的解决方法(亲测有效)》本文主要介绍了通过VMware新装的Linux系统没有IP地址的解决方法,主要步骤包括:关闭虚拟机、打开VM虚拟网络编辑器、还原VMnet8或修... 目录前言步骤0.问题情况1.关闭虚拟机2.China编程打开VM虚拟网络编辑器3.1 方法一:点击还原VM

查询SQL Server数据库服务器IP地址的多种有效方法

《查询SQLServer数据库服务器IP地址的多种有效方法》作为数据库管理员或开发人员,了解如何查询SQLServer数据库服务器的IP地址是一项重要技能,本文将介绍几种简单而有效的方法,帮助你轻松... 目录使用T-SQL查询方法1:使用系统函数方法2:使用系统视图使用SQL Server Configu

spoj705( 求不相同的子串个数)

题意:求串s的不同子串的个数 解题思路:任何子串都是某个后缀的前缀,对n个后缀排序,求某个后缀的前缀的个数,减去height[i](第i个后缀与第i-1 个后缀有相同的height[i]个前缀)。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstrin

浅谈主机加固,六种有效的主机加固方法

在数字化时代,数据的价值不言而喻,但随之而来的安全威胁也日益严峻。从勒索病毒到内部泄露,企业的数据安全面临着前所未有的挑战。为了应对这些挑战,一种全新的主机加固解决方案应运而生。 MCK主机加固解决方案,采用先进的安全容器中间件技术,构建起一套内核级的纵深立体防护体系。这一体系突破了传统安全防护的局限,即使在管理员权限被恶意利用的情况下,也能确保服务器的安全稳定运行。 普适主机加固措施:

【WebGPU Unleashed】1.1 绘制三角形

一部2024新的WebGPU教程,作者Shi Yan。内容很好,翻译过来与大家共享,内容上会有改动,加上自己的理解。更多精彩内容尽在 dt.sim3d.cn ,关注公众号【sky的数孪技术】,技术交流、源码下载请添加微信号:digital_twin123 在 3D 渲染领域,三角形是最基本的绘制元素。在这里,我们将学习如何绘制单个三角形。接下来我们将制作一个简单的着色器来定义三角形内的像素

XTU 1233 n个硬币连续m个正面个数(dp)

题面: Coins Problem Description: Duoxida buys a bottle of MaiDong from a vending machine and the machine give her n coins back. She places them in a line randomly showing head face or tail face o

两数之和--力扣1

两数之和 题目思路C++代码 题目 思路 根据题目要求,元素不能重复且不需要排序,我们这里使用哈希表unordered_map。注意题目说了只对应一种答案。 所以我们在循环中,使用目标值减去当前循环的nums[i],得到差值,如果我们在map中能够找到这个差值,就说明存在两个整数的和为目标值。 如果没有找到,就将当前循环的nums[i]以及下标i放入map中,以便后续查

CSS实现DIV三角形

本文内容收集来自网络 #triangle-up {width: 0;height: 0;border-left: 50px solid transparent;border-right: 50px solid transparent;border-bottom: 100px solid red;} #triangle-down {width: 0;height: 0;bor