塞进裤子ヾ(≧O≦)〃嗷~

0%

leetcode-976 三角形的最大周长

最初想法:

方法一:遍历三次,超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
def largestPerimeter(self, A):
"""
:type A: List[int]
:rtype: int
"""
#两边之和大于第三边,两边之差小于第三边
sorta = sorted(A)[::-1] #降序排序
for i in range(len(sorta)):
for j in range(i+1,len(sorta)):
for k in range(j+1,len(sorta)):
if self.judge(sorta[i],sorta[j],sorta[k]):
return sorta[i]+sorta[j]+sorta[k]
return 0

def judge(self,i,j,k): #判断是不是三角形
if i >= j+k or i-k >= j:
return False
return True

官方:

1
2
三角形变长满足任意两边之和大于第三边,任意两边之差小于第三边;
但实际上第二个条件已经包含在第一个条件里面了,所以我们只需要保证任意两边之和大于第三边就可以了。

使用break,跳出两层for循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution(object):
def largestPerimeter(self, A):
"""
:type A: List[int]
:rtype: int
"""
#两边之和大于第三边,两边之差小于第三边
sorta = sorted(A)[::-1] #降序排序
for i in range(len(sorta)-2):
for j in range(i+1,len(sorta)):
for k in range(j+1,len(sorta)):
if self.judge(sorta[i],sorta[j],sorta[k]):
return sorta[i]+sorta[j]+sorta[k]
#如果不满足i>j+k,说明比k小的更不满足
else:
break
#同样,比j小的更不会满足
else:
continue #对for i起作用
break #break跳出连续两层for循环

return 0

def judge(self,i,j,k): #判断是不是三角形
if i >= j+k:
return False
return True

最终版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
def largestPerimeter(self, A):
"""
:type A: List[int]
:rtype: int
"""
#两边之和大于第三边,两边之差小于第三边
sorta = sorted(A)[::-1] #降序排序
for i in range(len(sorta)-2):
if self.judge(sorta[i],sorta[i+1],sorta[i+2]):
return sorta[i]+ sorta[i+1]+sorta[i+2]

return 0

def judge(self,i,j,k): #判断是不是三角形
if i >= j+k:
return False
return True
if help:小手一抖点个广告 or 大手一挥资助一下