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

这篇具有很好参考价值的文章主要介绍了力扣:611. 有效三角形的个数。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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

力扣:611. 有效三角形的个数,leetcode,算法,职场和发展,学习方法


一、题目描述

力扣:611. 有效三角形的个数,leetcode,算法,职场和发展,学习方法通过题目的描述可以看出,意思是给定一个数组,然后观察数组中能元素组成三角形的个数!

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

力扣:611. 有效三角形的个数,leetcode,算法,职场和发展,学习方法


二、算法解析+代码!

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


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;
    }
};

力扣:611. 有效三角形的个数,leetcode,算法,职场和发展,学习方法

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

2.双指针思路

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

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

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

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

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

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

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

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

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


图解:

力扣:611. 有效三角形的个数,leetcode,算法,职场和发展,学习方法


代码如下:

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. 有效三角形的个数,leetcode,算法,职场和发展,学习方法

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

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

力扣:611. 有效三角形的个数,leetcode,算法,职场和发展,学习方法文章来源地址https://www.toymoban.com/news/detail-721112.html

到了这里,关于力扣:611. 有效三角形的个数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 「优选算法刷题」:有效三角形的个数

    给定一个包含非负整数的数组  nums  ,返回其中可以组成三角形三条边的三元组个数。 示例 1: 示例 2: 这道题,有一点挺新鲜的:构成三角形的三条边,仅需满足 2 条最短边之和大于等于第三条边即可。 以前的罗根,就总是傻傻地求 3 次😭 今天这道题,算是又打开了我新世

    2024年01月20日
    浏览(38)
  • 双指针算法实例5(有效三角形的个数)

    给定一个包含非负整数的数组  nums  ,返回其中可以组成三角形三条边的三元组个数。 示例 1: 示例 2: 提示: 1 = nums.length = 1000 0 = nums[i] = 1000 三角形构成条件:任意两边之和一定要大于第三边 其实在判断中,只需要判断 最小的两边和大于最长的一边 即可 假设 a=b=c 若要构成

    2024年02月11日
    浏览(41)
  • 【算法专题突破】双指针 - 有效三角形的个数(5)

    目录 1. 题目解析 2. 算法原理 3. 代码编写 写在最后: 题目链接:611. 有效三角形的个数 - 力扣(Leetcode)  我们可以根据示例1来理解这一道题目, 他说数组里面的数可以组成三角形三条边的个数, 那我们先自己枚举一下所有情况看看:  【2, 2, 3】  【2, 2, 4】  【2,

    2024年02月10日
    浏览(45)
  • 【算法挨揍日记】day03——双指针算法_有效三角形的个数、和为s的两个数字

       611. 有效三角形的个数 https://leetcode.cn/problems/valid-triangle-number/ 给定一个包含非负整数的数组  nums  ,返回其中可以组成三角形三条边的三元组个数。 本题是一个关于三角形是否能成立的题目,首先我们假设三角形的三边(a,b,c),我们要保证两边之和大于第三边    题

    2024年02月12日
    浏览(47)
  • 【编程题】有效三角形的个数

    给定一个包含非负整数的数组 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 构成三角形的条件 :任意两条边之和大于第三边,其

    2024年02月11日
    浏览(44)
  • 力扣120. 三角形最小路径和(Java 动态规划)

    Problem: 120. 三角形最小路径和 Problem:64. 最小路径和 本题目可以看作是在上述题目的基础上改编而来,具体的思路: 1.记录一个int类型的大小的 n 乘 n n乘n n 乘 n 的数组(其中 n n n 为数组triangle的行数)用于记录 每一个当前阶段的最小路径和 2.大体上可以依据题意得出动态转移

    2024年01月22日
    浏览(41)
  • Leetcode-976. 三角形的最大周长

    题目: 给定由一些正数(代表长度)组成的数组  nums  ,返回  由其中三个长度组成的、 面积不为零 的三角形的最大周长  。如果不能形成任何面积不为零的三角形,返回  0 。 示例 1: 示例 2: 提示: 3 = nums.length = 10^4 1 = nums[i] = 10^6 我一开始以为先排序,然后移动窗口

    2024年02月19日
    浏览(42)
  • 模型减面算法, 优化模型三角形

    sp4cerat/Fast-Quadric-Mesh-Simplification: Mesh triangle reduction using quadrics (github.com) https://github.com/sp4cerat/Fast-Quadric-Mesh-Simplification

    2023年04月24日
    浏览(32)
  • 面试算法100:三角形中最小路径之和

    在一个由数字组成的三角形中,第1行有1个数字,第2行有2个数字,以此类推,第n行有n个数字。例如,下图是一个包含4行数字的三角形。如果每步只能前往下一行中相邻的数字,请计算从三角形顶部到底部的路径经过的数字之和的最小值。从三角形顶部到底部的路径数字之和

    2024年01月16日
    浏览(43)
  • 用动态规划算法编程实现数字三角形问题

    如下所示为一个数字三角形: 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 请编一个程序计算从顶至底的某一条路径,使该路径所经过的数字的总和最大。 思路:建立两个二位数组m(用来存储数字三角形),sum(用来存储数字三角形中每一个值得路径值);sum[i] [j]从最后一行开始存储; 如果当前

    2024年02月11日
    浏览(61)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包