欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode976题解:三角形的最大周长以及C++中如何使用STL库中的sort排序api

程序员文章站 2022-04-01 14:46:49
...

题目:
给定由一些正数(代表长度)组成的数组 A,返回由其中三个长度组成的、面积不为零的三角形的最大周长。

如果不能形成任何面积不为零的三角形,返回 0。
示例 1:

输入:[2,1,2]
输出:5
示例 2:

输入:[1,2,1]
输出:0
示例 3:

输入:[3,2,3,4]
输出:10
示例 4:

输入:[3,6,2,3]
输出:8

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/largest-perimeter-triangle

解析
首先需要明确构成三角形的条件

两边之和大于第三边,两边之差小于第三边。

    bool is_triangle(int a,int b,int c){
        if(((a+b)>c)&&((a+c)>b)&&((b+c)>a)){
            if(((a-b)<c)&&((a-c)<b)&&((b-c)<a)&&((b-a)<c)&&((c-a)<b)&&((c-b)<a))
                return true;
            else
                return false;
        }
        return false;
    }
}

- 最直观简单的解法:
三层嵌套循环
先判断能不能成为三角形,再计算周长,与最大值对比,如果比当前最大值大,更新当前最大值以及相应的边。

class Solution {
public:
    bool is_triangle(int a,int b,int c){
        if(((a+b)>c)&&((a+c)>b)&&((b+c)>a)){
            if(((a-b)<c)&&((a-c)<b)&&((b-c)<a)&&((b-a)<c)&&((c-a)<b)&&((c-b)<a))
                return true;
            else
                return false;
        }
        return false;
    }
    int largestPerimeter(vector<int>& A) {
        int max=0;
        for(int i=0;i<A.size()-2;i++){
            for(int j = 1;j<A.size()-1;j++){
                for(int t =2;t<A.size();t++){
                    if(is_triangle(A[i],A[j],A[t])){
                        if(i!=j&&j!=t&&i!=t){
                            if((A[i]+A[j]+A[t])>max)
                                max = A[i]+A[j]+A[t];
                            }
                    }
                }
            }
        }  
        return max;
    }

};

结果:超出时间限制…

方法二:贪心 + 排序
不失一般性,我们假设三角形的边长满足 a \leq b \leq ca≤b≤c,那么这三条边组成面积不为零的三角形的充分必要条件为 a+b>c。

基于此,我们可以选择枚举三角形的最长边 c,而从贪心的角度考虑,我们一定是选「小于 c 的最大的两个数」作为边长 a 和 b,此时最有可能满足a+b>c,使得三条边能够组成一个三角形,且此时的三角形的周长是最大的。

因此,我们先对整个数组排序,倒序枚举第 i 个数作为最长边,那么我们只要看其前两个数 A[i-2] 和 A[i-1],判断 A[i−2]+A[i−1] 是否大于 A[i] 即可,如果能组成三角形我们就找到了最大周长的三角形,返回答案 A[i-2]+A[i-1]+A[i] 即可。如果对于任何数作为最长边都不存在面积不为零的三角形,则返回答案 0;

class Solution {
public:
    bool is_triangle(int a,int b,int c){
        if(((a+b)>c)&&((a+c)>b)&&((b+c)>a)){//两边之和大于第三边,两边之差小于第三边。
            if(((a-b)<c)&&((a-c)<b)&&((b-c)<a)&&((b-a)<c)&&((c-a)<b)&&((c-b)<a))
                return true;
            else
                return false;
        }
        return false;
    }
    int largestPerimeter(vector<int>& A) {
        sort(A.begin(),A.end()); //排序
        for(int i = A.size()-1;i>=2;i--){
            if(is_triangle(A[i],A[i-1],A[i-2]))
                return A[i]+A[i-1]+A[i-2];
        }
        return 0;
    }
};

总结:

      sort(A.begin(),A.end()); //排序

C++中有现成的排序算法sort()。

sort函数

1.sort函数包含在头文件为

#include <algorithm>

的c++标准库中,调用标准库里的排序方法可以实现对数据的排序,但是sort函数是如何实现的,我们不用考虑!

2.sort函数的模板有三个参数:

void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
(1)第一个参数first:是要排序的数组的起始地址。

(2)第二个参数last:是结束的地址(最后一个数据的后一个数据的地址)

(3)第三个参数comp是排序的方法:可以是从升序也可是降序。如果第三个参数不写,则默认的排序方法是从小到大排序。
例如:

 #include<iostream>
 #include<algorithm>
 using namespace std;
 main()
 {
    //sort函数第三个参数采用默认从小到大
     int a[]={45,12,34,77,90,11,2,4,5,55};
    sort(a,a+10);
    for(int i=0;i<10;i++)
       cout<<a[i]<<" ";     
} 

对于要倒序排列的,需要定义cmp函数:

#include<iostream>
#include<algorithm>
using namespace std;
bool cmp(int a,int b);
main(){
  //sort函数第三个参数自己定义,实现从大到小 
    int a[]={45,12,34,77,90,11,2,4,5,55};
      sort(a,a+10,cmp);
       for(int i=0;i<10;i++)
         cout<<a[i]<<" ";     
}
         //自定义函数
         bool cmp(int a,int b){
          return a>b;
}