976. Largest Perimeter Triangle

ゝ一纸荒年。 2022-04-25 01:20 136阅读 0赞

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:**

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

算法思想：

假设三个元素a,b,c，a>b>c,那么我们仅需比较b+c>a成立，那么就可以，即判断最小的两个数的值和是不是最大值就可以。那么我们只需要将数组从大到小排列，然后判断A\[i+1\]+A\[i+2\]>A\[i\]是否成立，成立，那么这三个数就是三角形的最大周长。

python代码：

class Solution:
        def largestPerimeter(self, A):
            """
            :type A: List[int]
            :rtype: int
            """
            A.sort(reverse=True)
            for i in range(len(A)-2):
                if A[i+2] + A[i+1] > A[i]:
                    return A[i] + A[i+1] + A[i+2]
                
            return 0

C代码：

int largestPerimeter(int* A, int ASize) {
        int i,j,key,max = 0;
        for(j=1;j<ASize;j++)
    	{
    		key=A[j];
    		i=j-1;
    		while(i>=0 && key<A[i])
    		{
    			A[i+1]=A[i];
    			i--;
    		}
    		A[i+1]=key;
    	}
        for(i=ASize-1;i>=2;i--)
        {
          if(A[i]<(A[i-1]+A[i-2]))
          {
            return max = A[i] + A[i-1] +A[i-2];
          }
        }
        return max;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，136人围观）

还没有评论，来说两句吧...

相关阅读

相关 # IMAGE - Image Perimeters

\ IMAGE - Image Perimeters \\ 题面翻译 \\\ 描述给出一张由"x"和"."组成的矩阵。每个"x"可以向上下左右及两个斜对角进行连通，请

深藏阁楼爱情的钟/ 2024年03月23日 14:23/ 0 赞/ 58 阅读

相关 463. Island Perimeter

463. Island Perimeter You are given a map in form of a two-dimensional integer grid w

た入场券/ 2022年07月12日 01:26/ 0 赞/ 157 阅读

相关 TRIANGLE

var vshader_src = 'attribute vec4 a_Position;\n\ void main()

清疚/ 2022年06月18日 00:52/ 0 赞/ 175 阅读

相关 [leetcode]: 463. Island Perimeter

1.题目 You are given a map in form of a two-dimensional integer grid where 1 represents

亦凉/ 2022年06月16日 01:07/ 0 赞/ 151 阅读

相关 Triangle

Triangle Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/

深碍√TFBOYSˉ_/ 2022年06月10日 13:27/ 0 赞/ 179 阅读

相关 Triangles

This is a simple problem. Given two triangles A and B, you should determine they are int

你的名字/ 2022年06月09日 03:45/ 0 赞/ 187 阅读

相关 976. Largest Perimeter Triangle

Given an array `A` of positive lengths, return the largest perimeter of a triangle with

ゝ一纸荒年。/ 2022年04月25日 01:20/ 0 赞/ 137 阅读

相关 island-perimeter

https://leetcode.com/problems/island-perimeter/ package com.company;

╰+哭是因爲堅強的太久メ/ 2022年03月30日 06:44/ 0 赞/ 135 阅读

相关 976-三角形的最大周长（Largest Perimeter Triangle）

题目描述中文：给定由一些正数（代表长度）组成的数组 A，返回由其中三个长度组成的、面积不为零的三角形的最大周长。如果不能形成任何面积不为零的三角形，返回 0。

男娘i/ 2022年01月26日 06:15/ 0 赞/ 238 阅读

相关 (Easy) Largest Perimeter Triangle LeetCode

Given an array `A` of positive lengths, return the largest perimeter of a triangle with

叁歲伎倆/ 2021年10月29日 10:46/ 0 赞/ 194 阅读