python给定一个包含非负整数的数组nums:(1)返回其中可以组成三角形三条边的三元组个数, 不存在返回None;(2)在能组成三角形的情况下,返回一个面积最大的三角形组合。
时间: 2023-05-27 09:02:54 浏览: 289
1. 计算三元组个数
根据三角形成立的条件,对于任意三条边 a,b,c,有以下关系:
a + b > c
a + c > b
b + c > a
因此,我们可以先对数组进行排序,然后固定最长的边 c,枚举另外两条边 a,b,判断是否能够组成三角形。如果能组成三角形,则可以组成三元组 (a,b,c)。
代码如下:
def triangleNum(nums):
if len(nums) < 3:
return None
nums.sort()
count = 0
for i in range(2, len(nums)):
left, right = 0, i - 1
while left < right:
if nums[left] + nums[right] > nums[i]:
count += right - left
right -= 1
else:
left += 1
return count
测试:
print(triangleNum([2, 2, 3, 4])) # 3
print(triangleNum([0, 0, 0])) # 1
print(triangleNum([1, 2, 3, 4, 5, 6])) # 7
print(triangleNum([1, 1])) # None
2. 计算面积最大的三角形
对于边长为 a,b,c 的三角形,根据海伦公式,其面积 S 为:
S = sqrt(p * (p-a) * (p-b) * (p-c))
其中 p = (a+b+c)/2 是半周长。
如果我们要求面积最大的三角形,实际上只需要枚举所有的三角形(也就是三元组),计算其面积,找到最大的那个即可。
代码如下:
import math
def maxArea(nums):
if len(nums) < 3:
return None
max_area = 0
for i in range(len(nums)-2):
for j in range(i+1, len(nums)-1):
for k in range(j+1, len(nums)):
if nums[i] + nums[j] > nums[k] and nums[i] + nums[k] > nums[j] and nums[j] + nums[k] > nums[i]:
p = (nums[i] + nums[j] + nums[k]) / 2
area = math.sqrt(p * (p - nums[i]) * (p - nums[j]) * (p - nums[k]))
if area > max_area:
max_area = area
max_triangle = (nums[i], nums[j], nums[k])
return max_triangle
测试:
print(maxArea([2, 2, 3, 4])) # (2, 3, 4)
print(maxArea([1, 2, 2, 3])) # (1, 2, 3)
print(maxArea([3, 4, 5])) # (3, 4, 5)
print(maxArea([1, 2, 3, 4, 5, 6])) # (3, 4, 5)
print(maxArea([1, 1])) # None
阅读全文