leetcode611-有效三角形的个数

原题

给定一个包含非负整数的数组,你的任务是统计其中可以组成三角形三条边的三元组个数。

示例1:

输入: [2,2,3,4] 输出: 3
解释:
有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3

注意:

  1. 数组长度不超过1000。
  2. 数组里整数的范围为 [0, 1000]。

解法

思想

三角形的某两边之和必须大于第三边且两边之差小于第三边

方法:

  1. 暴力:获取所有3元组,判断能否构成三角形
  2. 动态规划:先给数组排序,任意两个较小边之和必须大于第三边。

对于数组[1,3,4,5,6],先将最大边指向6,一最小边i指向1,一最小边j指向5,如下图所示。

leetcode611-有效三角形的个数

1+5不大于6,可以将最小边往后移一格。

leetcode611-有效三角形的个数

如图所示,此时3+5大于6,可以组成三角形,而因为数组是排序过的,则最小边再向后移最小两边之和也是大于第三边的,所以此时可以把总数加上j-i,然后把i还原回数组头部,j向前移一格

重复之前步骤,1+4不大于6,i向后移一格,3+4大于6,总数加上j-i

leetcode611-有效三角形的个数

代码

  1. 暴力
class Solution {
    public int triangleNumber(int[] nums) {
        int count = 0;
        for(int i = 0;i<nums.length-2;i++){
            for(int j = i+1;j<nums.length-1;j++){
                for(int n = j+1;n<nums.length;n++){
                    if(nums[i]+nums[j]>nums[n]&&Math.abs(nums[i]-nums[j])<nums[n]) count++;
                }
            }
        }        
        return count;
    }
}
  1. 动态规划
class Solution {
    public int triangleNumber(int[] nums) {
        int count = 0;
        Arrays.sort(nums);
        for(int n = nums.length-1;n>=2;n--){
            int i = 0;
            int j = n-1;
            while(i<j){
                if(nums[i]+nums[j]>nums[n]) {
                    count+=(j-i);
                    j--;
                }else{
                    i++;
                }
            }
        }     
        return count;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode611-%e6%9c%89%e6%95%88%e4%b8%89%e8%a7%92%e5%bd%a2%e7%9a%84%e4%b8%aa%e6%95%b0/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年2月7日
下一篇 2020年2月8日

相关推荐

  • leetcode72-编辑距离

    原题 给你两个单词 word1 和 word2 ,请你计算出将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作: 插入一个字符 删除一个字…

    2020年4月6日
    0110
  • leetcode40-组合总和II

    原题 给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字…

    算法 2020年5月2日
    0730
  • leetcode122-买卖股票的最佳时机II

    原题 给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。 注意: 你不能同…

    算法 2020年2月7日
    080
  • leetcode136-只出现一次的数字

    原题 给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。 说明: 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗…

    算法 2019年12月18日
    0150
  • leetcode117-填充每个节点的下一个右侧节点指针II

    原题 给定一个二叉树 struct Node {   int val;   Node *left;   Node *ri…

    2020年1月14日
    0370
  • leetcode1162-地图分析

    原题 你现在手里有一份大小为 N x N 的『地图』(网格) grid,上面的每个『区域』(单元格)都用 0 和 1 标记好了。其中 0 代表海洋,1 代表陆地,你知道距离陆地区域…

    2020年3月29日
    0170
  • leetcode409-最长回文串

    原题 给定一个包含大写字母和小写字母的字符串,找到通过这些字母构造成的最长的回文串。 在构造过程中,请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。 注意:假设字符串的长…

    算法 2020年3月19日
    0560
  • leetcode77-组合

    原题 给定两个整数 n 和 k,返回 1 ... n 中所有可能的 k 个数的组合。 示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], […

    算法 2020年5月12日
    0640
  • leetcode209-长度最小的子数组

    原题 给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组,返回 0。 示例: 输入: s = …

    算法 2019年11月20日
    0160
  • leetcode983-最低票价

    原题 在一个火车旅行很受欢迎的国度,你提前一年计划了一些火车旅行。在接下来的一年里,你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。 火车…

    算法 2020年5月6日
    0120

发表回复

登录后才能评论