題目
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: 5Example 2:
Input: [1,2,1]
Output: 0Example 3:
Input: [3,2,3,4]
Output: 10Example 4:
Input: [3,6,2,3]
Output: 8Note:
- 3 <= A.length <= 10000
- 1 <= A[i] <= 10^6
題目大意
找到可以組成三角形三條邊的長度，要求輸出三條邊之和最長的，即三角形周長最長。
解題思路
這道題也是排序題，先講所有的長度進行排序，從大邊開始往前找，找到第一個任意兩邊之和大於第三邊(滿足能構成三角形的條件)的下標，然後輸出這 3 條邊之和即可，如果沒有找到輸出 0 。�輸出 0 。
參考代碼
package leetcode
func largestPerimeter(A []int) int {
if len(A) < 3 {
return 0
}
quickSort164(A, 0, len(A)-1)
for i := len(A) - 1; i >= 2; i-- {
if (A[i]+A[i-1] > A[i-2]) && (A[i]+A[i-2] > A[i-1]) && (A[i-2]+A[i-1] > A[i]) {
return A[i] + A[i-1] + A[i-2]
}
}
return 0
}
func quickSort164(a []int, lo, hi int) {
if lo >= hi {
return
}
p := partition164(a, lo, hi)
quickSort164(a, lo, p-1)
quickSort164(a, p+1, hi)
}
func partition164(a []int, lo, hi int) int {
pivot := a[hi]
i := lo - 1
for j := lo; j < hi; j++ {
if a[j] < pivot {
i++
a[j], a[i] = a[i], a[j]
}
}
a[i+1], a[hi] = a[hi], a[i+1]
return i + 1
}