三角形的最大周长
程序员文章站
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;
}
};