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

三角形的最大周长

程序员文章站 2024-02-21 14:36:40
...

题目描述

三角形的最大周长

题解

给出两种解题思路,一种是回溯法,一种是贪心。

  • 回溯法

简单地说就是遍历所有可能的组合情况,可以用一个向量vector<int> shu 来存储三边的长度,使用标记符b 来判断是否集齐三边。b 初始值为0,shu 里每添加一个元素b 的值就加1,当b 的值为3时,集齐了三边,然后判断任意两边长度是否大于第三边,如果符合三角形的定义,就计算周长并赋值给res (这里res 只记录最大的周长值)。遍历完所有情况后res 里的值就是最大周长值。

缺点:时间复杂度太大

//回溯法
class Solution {
public:
    int res = 0;
    vector<int> shu;
    int b = 0;
    void back(vector<int>& A, int index) {
        if (b == 3) {
            if (shu[0] + shu[1] > shu[2] && shu[0] + shu[2] > shu[1] && shu[1] + shu[2] > shu[0]) {
                int sum = shu[0] + shu[1] + shu[2];
                if (sum > res) res = sum;
            }
            return;
        }
        for (int i = index; i < A.size(); i++) {
            shu.push_back(A[i]);
            b++;
            back(A, i + 1);
            b--;
            shu.pop_back();
        }

    }
    int largestPerimeter(vector<int>& A) {
        back(A, 0);
        return res;
    }
};
  • 贪心

首先对原数组进行排序,因为要找最大的周长,故从大向小找起,然后判断最小的的两边长度之和是否大于第三边,如果符合条件,则找到最优解,否则换另一个最大边进行判断。

//贪心
class Solution {
public:
    int largestPerimeter(vector<int>& A) {
        sort(A.begin(), A.end());
        for (int i = A.size() -1; i >= 2; i--) {
            if (A[i - 1] + A[i - 2] > A[i])
                return A[i] + A[i - 1] + A[i - 2];
        }
        return 0;
    }
};

三角形的最大周长