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

【LeetCode刷题笔记-21 976:三角形最大周长】

程序员文章站 2024-02-21 14:32:52
...

题目:
【LeetCode刷题笔记-21 976:三角形最大周长】
今天的题目确实很简单。

思路历程大概如下:

1.找三个最大数,然后判定

2.因为判定之后可能会不满足,所以要找次大数

3.那么要方便找最大数又要方便找次大数甚至次次大数,排序!

4.于是就有了先排序,再判定的方法。

5.判定只需要两个小边相加大于第三边即可。

C++代码附带测试:

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std; 

class Solution {
public:
    int largestPerimeter(vector<int>& A) {
    	if(A.size()<3)
    	{
    		return 0;
		}
		int ans = 0;
        sort(A.begin(),A.end());
        for(int i = A.size()-3;i>=0;i--)
        {
        	if(A[i]+A[i+1]>A[i+2])//两个较小边的和要大于第三边 
        	{
        		return A[i] + A[i+1] + A[i+2];
			} 
		}
		return 0;
    }
};


int main()
{
	vector<int> A = {1,2,3,4,5};
	Solution s;
	int ans = s.largestPerimeter(A);
	cout<<ans<<endl;
}

此外,我逛评论区还发现了一种优化方法,使用的冒泡排序。
因为Sort函数会直接排序所有的元素,但是我们要用的说不定只有后面的几个,前面的元素完全用不到。所以用冒泡排序用一个循环排一个会大大优化排序所使用的时间。

贴上冒泡排序的算法:

class Solution {
public:
    void bubble(vector<int> &A) //单次冒泡排序
    {
        for(int i=A.size()-1;i>0;i--)
        {
            if(A[i]>A[i-1])
                swap(A[i],A[i-1]);
        }
    }
    int largestPerimeter(vector<int>& A) {
        if(A.size()<3) return 0;
        int i=0;
        bubble(A);
        bubble(A);
        bubble(A);
        while(i<A.size()-2)
        {
            if(A[i+2]+A[i+1]>A[i])
                return A[i]+A[i+1]+A[i+2];
            bubble(A);
            i++;
        }
        return 0;
    }
};

经过测试,平均时间效率确实有得到提升。