【Leetcode 完整解答筆記】976. Largest Perimeter Triangle

我們需要找出陣列中可以形成的最大的三角形的周長。

我們先複習一下形成一個三角形的條件: 假設 a >= b >= c, 如果 a < b + c,則a , b, c 可以形成一個三角形。

Given an integer array nums, return the largest perimeter of a triangle with a non-zero area, formed from three of these lengths. If it is impossible to form any triangle of a non-zero area, return 0.

Example 1:

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

Example 2:

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

Example 3:

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

Example 4:

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

Constraints:

  • 3 <= nums.length <= 104
  • 1 <= nums[i] <= 106

解答思路:參考 leetcode @lee215

  1. 把陣列 A 裡的元素按大到小排序。
  2. 可以知道如果 -3 大的邊長(第三短的邊長)小於位置 -2 (第二短的邊長)以及 位置 -1 的邊長(最短的邊長),我們就可以得到一個三角形。也就是要符合 A[n-1] < A[n-2] + A[n-3]
  3. 而如果 A[n-1] >= A[n-2] + A[n-3] >= A[i] + A[j],將不會組成三角形。
  4. 針對剩下的數字重複第二 、第三步驟。

Python 解答:

class Solution:
    def largestPerimeter(self, A: List[int]) -> int:
        A = sorted(A)[::-1]
        for i in range(len(A) - 2):
            if A[i] < A[i + 1] + A[i + 2]:
                return A[i] + A[i + 1] + A[i + 2]
        return 0

假設輸入為 : [2, 1, 2]

A = sorted(A)[::-1]

經過排序後會變成 : [2, 2, 1]。

if A[i] < A[i + 1] + A[i + 2]:
    return A[i] + A[i + 1] + A[i + 2]

如果陣列 A 中最大的數字小於第 2 大和第 3 大的數字,就直接回傳他們之間的相加值。

我們再來看看 for 迴圈的條件,範圍在 len(A) – 2。

for i in range(len(A) - 2):

陣列 A 的之所以要減 2 ,是因為後面的定義 A[i] < A[i + 1] + A[i + 2]。如果陣列 A 的長度不事先減 2 ,就會超出陣列範圍,並出現 error。

Leave a Comment

Your email address will not be published. Required fields are marked *