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日

相关推荐

  • leetcode22-括号生成

    原题 数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。 示例: 输入:n = 3 输出:[ "((()))", "(()())", "…

    算法 2020年4月9日
    0130
  • leetcode84-柱状图中最大的矩形

    原题 给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。 求在该柱状图中,能够勾勒出来的矩形的最大面积。 以上是柱状图的示例,其中每个柱子的宽…

    2020年1月24日
    0100
  • leetcode445-两数相加II

    原题 给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。 你可以假设除了数字 0 之外,这两个数字都…

    算法 2020年4月14日
    0270
  • leetcode752-打开转盘锁

    原题 你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'。每个拨轮可以自由…

    2019年12月9日
    0280
  • leetcode733-图像渲染

    原题 有一幅以二维整数数组表示的图画,每一个整数表示该图画的像素值大小,数值在 0 到 65535 之间。 给你一个坐标 (sr, sc) 表示图像渲染开始的像素值(行 ,列)和一…

    2019年12月13日
    090
  • leetcode94-二叉树的中序遍历

    原题 给定一个二叉树,返回它的 中序 遍历。 示例: 输入: [1,null,2,3]  1   \    2 &nbs…

    算法 2019年12月12日
    01120
  • leetcode658-找到K个最接近的元素

    原题 给定一个排序好的数组,两个整数 k 和 x,从数组中找到最靠近 x(两数之差最小)的 k 个数。返回的结果必须要是按升序排好的。如果有两个数与 x 的差值一样,优先选择数值较…

    算法 2020年1月4日
    0110
  • leetcode35-搜索插入位置

    原题 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 你可以假设数组中无重复元素。 示例 1: 输入: […

    算法 2020年3月2日
    0120
  • leetcode217-存在重复元素

    原题 给定一个整数数组,判断是否存在重复元素。 如果任何值在数组中出现至少两次,函数返回 true。如果数组中每个元素都不相同,则返回 false。 示例1: 输入: [1,2,3…

    算法 2019年12月18日
    070
  • leetcode26-删除排序数组中的重复项

    原题 给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。 不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空…

    算法 2019年11月23日
    0180

发表回复

登录后才能评论