这是悦乐书的第 368 次更新, 第 396 篇原创
01 看题和准备
今天介绍的是 LeetCode 算法题中 Easy 级别的第 230 题(顺位题号是 976). 给定正长度的数组 A, 返回具有非零区域的三角形的最大周长, 由这些长度中的 3 个组成. 如果不可能形成任何非零区域的三角形, 则返回 0. 例如:
输入:[2,1,2]
输出: 5
输入:[1,2,1]
输出: 0
输入:[3,2,3,4]
输出: 10
输入:[3,6,2,3]
输出: 8
注意:
- 3 <= A.length <= 10000
- 1 <= A[i] <= 10^6
02 第一种解法
暴力解法, 会超时.
题目的意思是从数组中拿三个数组成三角形, 求最大周长, 如果找不到适合的数组成三角形, 就返回 0. 直接上循环, 取三个数, 拿到三个数后, 利用三角形的定义: 任意两边之和大于第三边, 任意两边之差小于第三边. 符合这两个条件就求三个数之和, 最后取其中的最大值输出.
此解法的时间复杂度是 O(N^3), 空间复杂度是 O(1).
- public int largestPerimeter(int[] A) {
- int max = 0, len = A.length;
- for (int i=0; i<=len-2; i++) {
- for (int j=i+1; j<len-1; j++) {
- for (int k=j+1; k<len; k++) {
- if (isTriangle(A[i], A[j], A[k])) {
- max = Math.max(max, A[i]+A[j]+A[k]);
- }
- }
- }
- }
- return max;
- }
- public boolean isTriangle(int x, int y, int z) {
- boolean f = false, f2 = false;
- // 任意两边之和大于第三边
- if (x+y>z && x+z>y && y+z>x) {
- f = true;
- }
- // 任意两边之差小于第三边
- if (x-y<z && x-z<y && y-z<x) {
- f2 = true;
- }
- return f && f2;
- }
03 第二种解法
第一种解法的时间复杂度太高了, 我们需要再优化下, 既然是数组, 并且需要一次拿三个数, 那能够想到的就是先排序了, 取相邻的三个元素, 以这三个元素作为三角形的边长 a,b,c, 他们的大小关系是 a<=b<=c, 如果想要 a,b,c 组成三角形, 需要满足什么条件?
第一种情况: 等边三角形, 即 a=b=c, 例如{3,3,3}.
第二种情况: 等腰三角形, 即 a=b 或者 b=c, 例如{4,4,5},{2,6,6}.
第三种情况: 普通三角形, 即 a<b<c, 例如 {3,4,5} 可以组成三角形, 但是像 {3,4,8} 就不能组成三角形, 虽然 3,4,8 满足 a<b<c 的关系.
所以, 如果有 a<=b<=c 的前提, 那么只要 a+b>c, 就可以组成三角形.
思路: 利用 Arrays 的 sort 方法, 对 A 排序, 从后往前每次取三个数, 判断是否满足 a+b>c, 满足此条件的三个数组成的三角形的周长是最大的.
此解法的时间复杂度是 O(NlogN), 空间复杂度是 O(1).
- public int largestPerimeter2(int[] A) {
- Arrays.sort(A);
- int n = A.length;
- for (int i=n-3; i>=0; i--) {
- if (A[i] + A[i+1]> A[i+2]) {
- return A[i] + A[i+1] + A[i+2];
- }
- }
- return 0;
- }
04 小结
算法专题目前已连续日更超过七个月, 算法题文章 236 + 篇, 公众号对话框回复[数据结构与算法] ,[算法] ,[数据结构] 中的任一关键词, 获取系列文章合集.
以上就是全部内容, 如果大家有什么好的解法思路, 建议或者其他问题, 可以下方留言交流, 点赞, 留言, 转发就是对我最大的回报和支持!
LeetCode.976 - 周长最大的三角形(Largest Perimeter Triangle)
来源: http://www.bubuko.com/infodetail-3109378.html