[已解决]Python：每日一题 288

zltzlt

今天的题目：

给定一个整数数组，在该数组中，寻找三个数，分别代表三角形三条边的长度，求可以寻找到多少组这样的三个数来组成三角形。

示例 1：

输入：[3, 4, 6, 7]
输出：3
解释：可以组成的是 (3, 4, 6)，(3, 6, 7)，(4, 6, 7)。

示例 2：

输入：[4, 4, 4, 4]
输出：4
解释：任何三个数都可以构成三角形，所以答案为 C³₄ = 4。

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

Stubborn

2019-12-12 19:33:48

1. def modify(nums: list):
   
2.     length = len(nums)
   
3.     if len(nums) < 3: return 0
   
4.     nums.sort()
   
5.     result = 0
   
6.     for c in range(length-1, 1, -1):
   
7.         a = 0
   
8.         b = c - 1
   
9.         while a < b:
   
10.             if nums[a] + nums[b] > nums[c]:
    
11.                 result += b - a
    
12.                 b -= 1
    
13.             else:
    
14.                 a += 1
    
15.     return result
    

复制代码

跳转到最佳答案楼层

冬雪雪冬

1. def fun(lst):
   
2.     import itertools
   
3.     count = 0
   
4.     for i in itertools.combinations(lst, 3):
   
5.         list1 = list(i)
   
6.         list1.sort()
   
7.         if list1[0] + list1[1] > list1[2]:
   
8.             count += 1
   
9.     return count

复制代码

18463102026

1. from itertools import combinations,filterfalse
   
2. from functools import lru_cache
   
3. @lru_cache()
   
4. def fun3(s):
   
5.     return len(list(filterfalse(lambda x:not(x[0]+x[1] >x[2] and abs(x[0]-x[1]) <x[2]) ,combinations(s,3))

复制代码

danteer

严格来说示例二只有(4,4,4)这一组数可以组成三角形，应该是1才对啊？？？

1. def fun(nums):
   
2.     result = 0
   
3.     if len(nums) < 3:
   
4.         return result
   
5.     import itertools
   
6.     for each in itertools.combinations(nums,3):
   
7.         if max(each) * 2 < sum(each):
   
8.             result += 1
   
9.     return result

复制代码

1. def func2(nums):
   
2.     nums.sort()
   
3.     result = 0
   
4.     for each in set(nums):
   
5.         if nums.count(each) > 3:
   
6.             temp = nums.count(each)
   
7.             while temp > 3:
   
8.                 nums.remove(each)
   
9.                 temp -= 1
   
10.     while nums[2] >= nums[1] + nums[0] and len(nums) >= 3:
    
11.         nums.pop(0)
    
12.     while nums[-1] >= nums[-2] + nums[-3] and len(nums) >= 3:
    
13.         nums.pop(-1)
    
14.     if len(nums) < 3:
    
15.         return result
    
16.     for i in range(len(nums)-2):
    
17.         for j in range(i+1,len(nums)-1):
    
18.             for k in range(j+1,len(nums)):
    
19.                 if max(nums[i],nums[j],nums[k]) * 2 < nums[i] + nums[j] + nums[k]:
    
20.                     result += 1
    
21.                 else:
    
22.                     break
    
23.     return result
    
24.    

复制代码

TJBEST

1. def fun(inputList):
   
2.     if len(inputList)<3:
   
3.         return 0
   
4.     else:
   
5.         count = 0#计数
   
6.         numSet = set(inputList)
   
7.         keyList = sorted(numSet)
   
8.         valueList = []
   
9.         for each in keyList:
   
10.             valueList.append(inputList.count(each))
    
11.         #1等边三角形
    
12.         indexA = 0
    
13.         while indexA < len(keyList):
    
14.             if valueList[indexA]>2:
    
15.                 n = valueList[indexA]
    
16.                 count = count + n*(n-1)*(n-2)//6
    
17.             indexA = indexA + 1
    
18.         #2等腰非等边
    
19.         indexA = 0
    
20.         while indexA < len(keyList):
    
21.             if valueList[indexA]>1:
    
22.                 n = valueList[indexA]
    
23.                 count = count + (n*(n-1)//2)*(len(inputList)-valueList[indexA])
    
24.             indexA = indexA + 1
    
25.         #3一般三角
    
26.         indexA = 0
    
27.         while indexA < (len(keyList)-2):
    
28.             indexB = indexA + 1
    
29.             while indexB < (len(keyList)-1):
    
30.                 indexC = indexB + 1
    
31.                 while indexC < len(keyList):
    
32.                     if (keyList[indexA]+keyList[indexB])>keyList[indexC]:
    
33.                         count = count + valueList[indexA]*valueList[indexB]*valueList[indexC]
    
34.                         indexC = indexC + 1
    
35.                     else:
    
36.                         break
    
37.                 indexB = indexB + 1
    
38.             indexA = indexA + 1
    
39.         return count
    

复制代码

凌九霄

又是效率题吧

Croper

只需要考虑 最短边+次短边>最长边 一个条件

从次短边开始考虑，可以把列表分为两部分
每个长度的最短边都可以对应一个最大长边长度，只要最长边小于这个长度，都可以形成三角形

时间复杂度应该在O[n^2]

1. def solution(l):
   
2.         l.sort()
   
3.         N=len(l)
   
4.         ret=0
   
5.         for b in range(1,N-1):
   
6.             k=0
   
7.             a=0
   
8.             c=b+1
   
9.             while (a<b and c<N):
   
10.                 if (l[a]+l[b]<=l[c]):
    
11.                     ret+=k
    
12.                     a+=1
    
13.                 else:
    
14.                     c+=1
    
15.                     k+=1
    
16.             ret+=k*(b-a)
    
17. 
    
18.         return ret
    

复制代码

闲愚

1. from itertools import combinations
   
2. 
   
3. def solve(s):
   
4.     count = 0
   
5.     for member in combinations(s,3):
   
6.         item = list(member)
   
7.         for i in range(3):
   
8.             if item[0] >= item[1] + item [2] or item[0] < abs(item[1] - item[2]):
   
9.                 break
   
10.             a = item[0]
    
11.             item.remove(a)
    
12.             item.append(a)
    
13.         else:
    
14.             count += 1
    
15.             print(member)
    
16.     return count
    
17. 
    
18. 
    
19. if __name__ == '__main__':
    
20.     print('自测1：输入：[3, 4, 6, 7],输出：')
    
21.     print(solve([3,4,6,7]))
    
22. 
    
23.     print('自测2：输入：[4, 4, 4, 4],输出：')
    
24.     print(solve([4,4,4,4]))
    
25. 
    
26.     print('自测3：输入：[0, 0, 0, 0],输出：')
    
27.     print(solve([0,0,0,0]))
    

复制代码

零0℃度

1. def f288(lst):
   
2.     lst.sort()
   
3.     n = len(lst)
   
4.     count = 0
   
5.     for i in range(n-2):
   
6.         for j in range(i+1,n-1):
   
7.             count += len([x for x in lst[j+1:] if x<lst[i]+lst[j]])
   
8.     return count

复制代码

不用 itertools 得两层for循环了

hrp

1. # 逻辑思维不好找不到技巧只能暴力解决了，可能会超时
   
2. def func288(intlist):
   
3.     templist, result = [], []
   
4.     if len(intlist) >= 3:
   
5.         for n in range(len(intlist)):
   
6.             templist.append((intlist[n], n))
   
7.         for i in templist:
   
8.             templist1 = templist * 1
   
9.             templist1.remove(i)
   
10.             for i1 in templist1:
    
11.                 templist2 = templist1 * 1
    
12.                 templist2.remove(i1)
    
13.                 for i2 in templist2:
    
14.                     numlist = [i, i1, i2]
    
15.                     numlist.sort()
    
16.                     if not numlist in result:
    
17.                         if i[0] < (i1[0] + i2[0]) and i[0] > abs(i1[0] - i2[0]):
    
18.                             result.append(numlist)
    
19.     return len(result)
    

复制代码

阴阳神万物主

这我来个递归吧。

1. def solve(nums:'整数列表',side=0,bs=0,bd=0)->int:
   
2.     res = 0
   
3.     for i in range(len(nums)):
   
4.         each = nums[i]
   
5.         if side == 2:
   
6.             if bs > each and bd < each:
   
7.                 res += 1
   
8.         elif side:
   
9.             res += solve(nums[i+1:],side+1,bs+each,abs(bd-each))
   
10.         else:
    
11.             res += solve(nums[i+1:],side+1,each,each)
    
12.     return res
    
13. if __name__ == '__main__':
    
14.     print('示例1 输出：',solve([3,4,6,7]))
    
15.     print('示例2 输出：',solve([4,4,4,4]))
    
16. 
    

复制代码

逻辑上应该没问题，时间复杂度应该是 O(n!)

776667

1. from itertools import combinations
   
2. 
   
3. def fun288(x):
   
4.     return len([i for i in combinations(x,3) if sorted(i)[0]+sorted(i)[1]>sorted(i)[2]])

复制代码

指头比思想慢

哈哈哈，来测试一下我这个的速度

1. def count_triangle(this_list):
   
2.     this_list.sort()
   
3.     count = 0
   
4.     list_len = len(this_list)
   
5.     for i in range(list_len-2):
   
6.         L = i + 1
   
7.         R = L + 1
   
8.         while L < list_len-1:
   
9.             if this_list[i] + this_list[L] <= this_list[R]:
   
10.                 L += 1
    
11.                 R = L + 1
    
12.             else:
    
13. #                 print('组合值:', this_list[i], this_list[L], this_list[R])
    
14. #                 print('下  标:', i, L, R)
    
15.                 count += 1
    
16.                 if R == list_len-1:
    
17.                     L += 1
    
18.                     R = L + 1
    
19.                 else:
    
20.                     R += 1
    
21.     print('count:',count,'\n')
    
22.    
    
23. if __name__ == '__main__':
    
24.     count_triangle([4, 4, 4, 4])
    
25.     count_triangle([1, 2, 3, 4])
    
26.     count_triangle([9, 2, 2, 3, 5, 6,9, 2, 2, 3, 5, 6,9, 2, 2, 3, 5, 6,9, 2, 2, 3, 5, 6,9, 2, 2, 3, 5, 6,9, 2, 2, 3, 5, 6,9, 2, 2, 3, 5, 6,9, 2, 2, 3, 5, 6,9, 2, 2, 3, 5, 6,9, 2, 2, 3, 5, 6,9, 2, 2, 3, 5, 6,9, 2, 2, 3, 5, 6,9, 2, 2, 3, 5, 6,9, 2, 2, 3, 5, 6,9, 2, 2, 3, 5, 6,9, 2, 2, 3, 5, 6,9, 2, 2, 3, 5, 6,9, 2, 2, 3, 5, 6,9, 2, 2, 3, 5, 6,9, 2, 2, 3, 5, 6,9, 2, 2, 3, 5, 6,9, 2, 2, 3, 5, 6,9, 2, 2, 3, 5, 6,9, 2, 2, 3, 5, 6,9, 2, 2, 3, 5, 6,9, 2, 2, 3, 5, 6,9, 2, 2, 3, 5, 6,9, 2, 2, 3, 5, 6,11])

复制代码

Stubborn

1. def modify(nums: list):
   
2.     length = len(nums)
   
3.     if len(nums) < 3: return 0
   
4.     nums.sort()
   
5.     result = 0
   
6.     for c in range(length-1, 1, -1):
   
7.         a = 0
   
8.         b = c - 1
   
9.         while a < b:
   
10.             if nums[a] + nums[b] > nums[c]:
    
11.                 result += b - a
    
12.                 b -= 1
    
13.             else:
    
14.                 a += 1
    
15.     return result
    

复制代码

zltzlt

冬雪雪冬 发表于 2019-12-11 22:10

输入 list(range(1, 1000)) 超时

zltzlt

18463102026 发表于 2019-12-11 22:27

右边漏了两个括号，我给补上了

zltzlt

18463102026 发表于 2019-12-11 22:27

TypeError: unhashable type: 'list'

zltzlt

danteer 发表于 2019-12-11 22:35
严格来说示例二只有(4,4,4)这一组数可以组成三角形，应该是1才对啊？？？

第一个输入 list(range(1, 1000)) 超时

zltzlt

凌九霄 发表于 2019-12-11 23:37
又是效率题吧

嗯

zltzlt

TJBEST 发表于 2019-12-11 23:08

输入 list(range(1, 1000)) 超时