[Swift]LeetCode976.三角形的最大周长|LargestPerimeterTriangle

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10262240.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given an array A of positive lengths, return the largest perimeter of a triangle with non-zero area, formed from 3 of these lengths.

If it is impossible to form any triangle of non-zero area, return 0.

Example 1:

Input: [2,1,2]
Output: 5

Example 2:

Input: [1,2,1]
Output: 0

Example 3:

Input: [3,2,3,4]
Output: 10

Example 4:

Input: [3,6,2,3]
Output: 8

Note:

3 <= A.length <= 10000
1 <= A[i] <= 10^6

给定由一些正数（代表长度）组成的数组 A，返回由其中三个长度组成的、面积不为零的三角形的最大周长。

如果不能形成任何面积不为零的三角形，返回 0。

示例 1：

输入：[2,1,2]
输出：5

示例 2：

输入：[1,2,1]
输出：0

示例 3：

输入：[3,2,3,4]
输出：10

示例 4：

输入：[3,6,2,3]
输出：8

提示：

3 <= A.length <= 10000
1 <= A[i] <= 10^6

276ms

 1 class Solution {
 2     func largestPerimeter(_ A: [Int]) -> Int {
 3         var best = 0
 4         var A = A
 5         A.sort(by: >)
 6         for i in 0..<A.count-2 {
 7             let j = i+1
 8             let k = j+1
 9             if A[i]+A[j]>A[k] && A[i]+A[k]>A[j] && A[j]+A[k]>A[i] {
10                 best = max(best,A[i]+A[j]+A[k])
11             }
12         }
13         return best
14     }
15 }

308ms

 1 class Solution {
 2     func largestPerimeter(_ A: [Int]) -> Int {
 3         var sortedA = A.sorted()
 4         
 5         var i = A.count - 1
 6         var j = i - 1
 7         var k = j - 1
 8     
 9         while k >= 0 && sortedA[j] + sortedA[k] <= sortedA[i] {
10             i -= 1
11             j -= 1
12             k -= 1
13         }
14         
15         return k >= 0 ? sortedA[i] + sortedA[j] + sortedA[k] : 0
16     }
17 }

312ms

 1 class Solution {
 2     func largestPerimeter(_ A: [Int]) -> Int {
 3         var A = A
 4         A.sort()
 5         for i in (2...A.count-1).reversed(){
 6             if(A[i] < A[i-1] + A[i-2]){
 7                 return A[i] + A[i-1] + A[i-2]
 8             }
 9         }
10         return 0
11     }
12 }

324ms

 1 class Solution {
 2     func largestPerimeter(_ A: [Int]) -> Int {        
 3         var A = A.sorted(by:<)
 4         var n = A.count
 5         for i in stride(from:n-3,through:0,by:-1)
 6         {
 7             if A[i] + A[i+1] > A[i+2]
 8             {
 9                 return A[i] + A[i+1] + A[i+2]
10             }
11         }
12         return 0
13     }
14 }

328ms

 1 class Solution {
 2 func largestPerimeter(_ A:[Int]) -> Int {
 3     return compare(A.sorted(by: > ))
 4 }
 5 func compare(_ array:[Int]) -> Int {
 6     if array[0] >= array[1] + array[2] {
 7         if array.count == 3 {
 8             return 0
 9         } else{
10             var new = array
11             new.removeFirst()
12             return compare(new)
13         }
14     } else {
15         return array[0] + array[1] + array[2]
16     }
17   }
18 }