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

zltzlt

闲愚 发表于 2019-12-12 00:06

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

zltzlt

零0℃度 发表于 2019-12-12 08:11
不用 itertools 得两层for循环了

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

zltzlt

hrp 发表于 2019-12-12 08:24

输入 [13997,34317,37086,20473,38080,37213,20462,16113,3627,28916,18923,34673,12736,28219,14492,5626,36179,36641,7144,15610,26209,24202,15373,18773,8821,34278,27891,7439,28245,33679,26343,13790,15439,31961,25859,10679,17776,37552]超时

zltzlt

阴阳神万物主 发表于 2019-12-12 10:29
这我来个递归吧。

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

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

zltzlt

776667 发表于 2019-12-12 10:33

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

zltzlt

指头比思想慢 发表于 2019-12-12 13:01
哈哈哈，来测试一下我这个的速度

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

阴阳神万物主

Stubborn 发表于 2019-12-12 19:33

哦呦！！！我怎么就没想到排序呢。
这招是真的高。

fan1993423

Stubborn 发表于 2019-12-12 19:33

我讲究你的代码写了个验证函数

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.                 print(a,b,c)
    
13.                 print(result)
    
14.                 b -= 1
    
15.             else:
    
16.                 a += 1
    
17.     return result
    
18. modify([1,2,4,5,6])
    

复制代码

我想问的是，这个只找出了a,b,c两组：1,3,4和1,2,3。但是2,3,4也是可以，但没有体现，另外在1,3,4那里b-a=2，为什么这个地方result要加2

fan1993423

阴阳神万物主 发表于 2019-12-12 21:21
哦呦！！！我怎么就没想到排序呢。
这招是真的高。

因为你做题就想到递归这个深奥的东西

阴阳神万物主

fan1993423 发表于 2019-12-13 15:40
因为你做题就想到递归这个深奥的东西

请容我弱弱的说一句：递归的思路很简单啊……

Stubborn

fan1993423 发表于 2019-12-13 15:38
我讲究你的代码写了个验证函数
我想问的是，这个只找出了a,b,c两组：1,3,4和1,2,3。但是2,3,4也是可以 ...

你应该要搞懂，为什么可以用b - a 去代表结果进行累加，而不是什么要加 2 ！

fan1993423

1. def fun288(n):
   
2.     length=len(n)
   
3.     count=0
   
4.     for a in range(length):
   
5.         b=a+1
   
6.         while b<=length-2:
   
7.             c=b+1
   
8.             while c<=length-1:
   
9.                 if n[a]+n[b]>n[c]:
   
10.                     count+=1
    
11.                 c+=1
    
12.             b+=1
    
13.     return count

复制代码

fan1993423

Stubborn 发表于 2019-12-13 16:21
你应该要搞懂，为什么可以用b - a 去代表结果进行累加，而不是什么要加 2 ！

来说说，我比较糊，我自己写的是三重循环，但很好理解

Stubborn

fan1993423 发表于 2019-12-13 17:25
来说说，我比较糊，我自己写的是三重循环，但很好理解

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.             """  
    
11.             [1,     2,      4,      5,      6]
    
12.                     a               b       c
    
13.             b - a 表示这个区间类都可以被组成三角形
    
14.             包括 256 456
    
15.             """
    
16.             if nums[a] + nums[b] > nums[c]:
    
17.                 result += b - a
    
18.                 print(a,b,c)
    
19.                 print(result)
    
20.                 b -= 1
    
21.             else:
    
22.                 a += 1
    
23.     return result
    

复制代码

fan1993423

Stubborn 发表于 2019-12-13 18:10

懂了，思路比较巧妙