190.Largest Perimeter Triangle

本文主要是介绍190.Largest Perimeter Triangle，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

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

链接

https://leetcode.com/problems/largest-perimeter-triangle/

分析

输入的是一个数组，首先对数组从大到小进行排序，对于任意相邻三个数字，如果前面两个的差值小于第三个，那么这三个就是题目要求的最大周长的值；
基于如下两点考虑：
(1).题目要求返回最长，则按照从大到小的顺序排序后，则找到一个满足三角形特性的就可以返回了。
(2).如果连续三个数字(a>b>c)，不能满足三角形特性(a - b > c)，那么再往c的后一个更不可能找到了。
思考：
根据这个题目可以衍生出一道，给定一个整型数字，返回可以拼接成三角形的个数。
解决方案和上面一个，先排序，对于任意相邻的两个数字 a 和 b，找到所有可以满足a - b > c 的 c 的个数，最后累加这些个数即可；

code

class Solution(object):def largestPerimeter(self, A):""":type A: List[int]:rtype: int""""""三角形特性：任意两条边之和大于第三边，为了防止加法溢出，可以使用任意两边之差小于第三边的特性；输入的是一个数组，首先对数组从大到小进行排序，对于任意相邻三个数字，如果前面两个的差值小于第三个，那么这三个就是题目要求的最大周长的值；基于如下两点考虑：(1).题目要求返回最长，则按照从大到小的顺序排序后，则找到一个满足三角形特性的就可以返回了。(2).如果连续三个数字(a>b>c)，不能满足三角形特性(a - b > c)，那么再往c的后一个更不可能找到了。"""A.sort(reverse=True)for i in range(0, len(A) - 2):if A[i] - A[i+1] < A[i + 2]:return A[i] + A[i+1] + A[i + 2]return 0

这篇关于190.Largest Perimeter Triangle的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---