私人诊所网站源码,建设厅网站ca验证失败,公司建设网站的申请信用卡,制作网站培训学校朋友们、伙计们#xff0c;我们又见面了#xff0c;本专栏是关于各种算法的解析#xff0c;如果看完之后对你有一定的启发#xff0c;那么请留下你的三连#xff0c;祝大家心想事成#xff01; C 语 言 专 栏#xff1a;C语言#xff1a;从入门到精通 数据结构专栏我们又见面了本专栏是关于各种算法的解析如果看完之后对你有一定的启发那么请留下你的三连祝大家心想事成 C 语 言 专 栏C语言从入门到精通 数据结构专栏数据结构 个 人 主 页 stackY、 C 专 栏 C Linux 专 栏 Linux 目录
1. 题目解析
2. 算法思路
3. 代码实现
4. 算法复杂度 1. 题目解析 Leetcode611.有效三角形的个数https://leetcode.cn/problems/valid-triangle-number/ 题目描述 给定一个包含非负整数的数组 nums 返回其中可以组成三角形三条边的三元组个数。 示例 1: 输入: nums [2,2,3,4]
输出: 3
解释:有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3示例 2: 输入: nums [4,2,3,4]
输出: 4 判断是否为三角形两边之和大于第三边首先想到的就是暴力求解依次进行比较但是这样的方法代价太高根据有序的三个数判断是否能构成三角形可以使用较小的两个数之和与较大的一个数进行比较若成立则能构成三角形。所以可以先对数组排序再选取数据进行判断。 2. 算法思路 首先使用sort对数据进行有序处理 然后使用双指针算法再加上单调性进行判断首先确定一个最大值为max第三条边在max的左区间设置两个指针left指向最右边的值right指向最右边的值判断left与right之和与max的大小如果max大于它由于right左边的值都比right小所以right没必要--所以只要让left即可。 如果max小于它由于left右边的值都比left大所以left与right之间的数都可以与max组成三角形所以只要让right--即可。 当left和right相遇时再使用次大的作为第三条边依次类推直到整个数组只剩下三个元素再判断最后一次就停止。 3. 代码实现 class Solution {
public:int triangleNumber(vectorint nums) {//1.先排序sort(nums.begin(), nums.end());//2.确定第三条边利用双指针依次判断比较int left, right;int Max nums.size()-1;int count 0;while(Max 2) //剩下最后一组再判断一次即可{right Max-1;left 0;while(left right){if(nums[left] nums[right] nums[Max]){count (right - left);right--;}else{left;}}Max--; }return count;}
}; 4. 算法复杂度 时间复杂度O(N^2) 空间复杂度O(1) 朋友们、伙计们美好的时光总是短暂的我们本期算法的分享就到此结束欲知后事如何请听下回分解~最后看完别忘了留下你们弥足珍贵的三连喔感谢大家的支持
