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日

相关推荐

  • leetcode106-从中序与后序遍历序列构造二叉树

    原题 根据一棵树的中序遍历与后序遍历构造二叉树。 注意:你可以假设树中没有重复的元素。 例如,给出 中序遍历 inorder = [9,3,15,20,7] 后序遍历 postor…

    算法 2020年1月13日
    0380
  • leetcode695-岛屿的最大面积

    原题 给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围…

    算法 2020年3月15日
    01230
  • leetcode35-搜索插入位置

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

    算法 2020年3月2日
    0120
  • leetcode62-不同路径

    原题 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Fi…

    2020年2月21日
    0380
  • leetcode403-青蛙过河

    原题 一只青蛙想要过河。 假定河流被等分为 x 个单元格,并且在每一个单元格内都有可能放有一石子(也有可能没有)。 青蛙可以跳上石头,但是不可以跳入水中。 给定石子的位置列表(用单…

    算法 2020年6月16日
    04640
  • 蓝桥杯试题-大小写转换

    原题 资源限制 时间限制:1.0s 内存限制:256.0MB 问题描述   输入一个字符串,将大写字符变成小写、小写变成大写,然后输出 输入格式 acbAB 输出格式 ACBab …

    算法 2020年2月29日
    080
  • leetcode221-最大正方形

    原题 在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。 示例: 输入: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 …

    算法 2020年5月8日
    0110
  • leetcode23-合并K个排序链表

    原题 合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2->3->…

    算法 2020年2月4日
    0170
  • leetcode264-丑数II

    原题 编写一个程序,找出第 n 个丑数。 丑数就是只包含质因数 2, 3, 5 的正整数。 示例: 输入: n = 10 输出: 12 解释: 1, 2, 3, 4, 5, 6, …

    算法 2020年2月10日
    0190
  • 剑指offer13-机器人的运动范围

    原题(来源Leetcode) 地上有一个m行n列的方格,从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动,它每次可以向左、右、上、下…

    算法 2020年4月8日
    0110

发表回复

登录后才能评论