题目:
给定由一些正数(代表长度)组成的数组 A,返回由其中三个长度组成的、面积不为零的三角形的最大周长。
如果不能形成任何面积不为零的三角形,返回 0。
示例:
输入:[3,6,2,3]
输出:8
解题方法:
这道题刚开始没有什么思路,因为判断三角形的条件是:
a+b >c 任意两条边之和大于第三条边。
每次选三个数出来然后做三次判断,光想想都觉得代码很复杂。后来又想了一下(没看题解),感觉似乎没有那么麻烦,只需要排个序,然后找最大的三个数判断一下就行了。思路就是判断三个数中较小的两个数之和是否大于最大数,如果大于就是三角形,否则就不是。然后类似滑窗,排除最大的数,添加数组中没有使用过的数中的最大值,一直判断到符合条件为止。
代码和结果:
class Solution {
public:
int largestPerimeter(vector<int>& A) {
sort(A.begin(),A.end());
int i=A.size();
while(i>2)
{
if(A[i-1]<A[i-2]+A[i-3])
return A[i-1]+A[i-2]+A[i-3];
else
i--;
}
return 0;
}
};
运行结果:结果不是太好,速度并不是很理想,但是我觉得我自己能想到这种方法应该已经是不看题解的极限了,那就不深究了。
原题链接:https://leetcode-cn.com/problems/largest-perimeter-triangle/