Python: 每日一题 43
本帖最后由 ooxx7788 于 2017-5-11 18:03 编辑给定一个由数值组成的列表(array)和一个整数(interger),返回列表中相加之和等于整数的两个数。
列表长度最长为1000万，用时不超过12秒(好像是1.2秒,还是7秒,好烦没有给出明确时间)。
由于这个编辑器的关系,我实在没有办法正常对齐,所以你们就将就着看吧.
sum_pairs(, 10)
# ^-^ 3 + 7 = 10
==
sum_pairs(, 6)
# ^---^ 4 + 2 = 6, index: 0, 2 *
# ^---^ 3 + 3 = 6, index: 1, 3
# ^---^ 2 + 4 = 6, index:2, 4
#* 返回整体最早出现的答案
==
sum_pairs(, 2)
#没有可以相加成2的组合.
== None
sum_pairs(, 10)
# ^--------^ 5 + 5 = 10, index: 1, 5
# ^-^ 3 + 7 = 10, index: 3, 4 *
#* 返回整体最早出现的答案
==
测试代码:
先更新一些test.py
def assert_equals(func, target, *args):
if func == target:
print('Success！')
else:
print('Fail!{0} not equals {1}'.format(func, target))
print(*args)
l1 =
l2 =
l3 =
l4 =
l5 =
l6 =
l7 =
l8 =
test.assert_equals(sum_pairs(l1, 8), , "Basic: %s should return for sum = 8" % l1)
test.assert_equals(sum_pairs(l2, -6), , "Negatives: %s should return for sum = -6" % l2)
test.assert_equals(sum_pairs(l3, -7), None, "No Match: %s should return None for sum = -7" % l3)
test.assert_equals(sum_pairs(l4, 2), , "First Match From Left: %s should return for sum = 2 " % l4)
test.assert_equals(sum_pairs(l5, 10), ,
"First Match From Left REDUX!: %s should return for sum = 10 " % l5)
test.assert_equals(sum_pairs(l6, 8), , "Duplicates: %s should return for sum = 8" % l6)
test.assert_equals(sum_pairs(l7, 0), , "Zeroes: %s should return for sum = 0" % l7)
test.assert_equals(sum_pairs(l8, 10), , "Subtraction: %s should return for sum = 10" % l8)
**** Hidden Message *****
def sum_pairs(array=,interger=10):
jg=[]
njg=[]
l=len(array)
x=1
for i in range(l-1,0,-1):
if i<2:x=0
for j in range(i-1,-1,-1):
if array+array==interger:
jg=,array,j,i]
if x:
njg=sum_pairs(array[:jg],interger)
if jg==[]:
return []
elif njg==[]:
return str(jg)+'+'+str(jg)+'='+str(interger)+',index:'+str(jg)+','+str(jg)
else:
return str(njg)+'+'+str(njg)+'='+str(interger)+',index:'+str(njg)+','+str(njg)
print(sum_pairs(,10)) 本帖最后由 ooxx7788 于 2017-5-11 11:48 编辑
余欲渔 发表于 2017-5-11 10:42
(, -7)
不能返回正确的结果.
查明白了,应该返回None,但是你返回的是[]。到不是程序问题。 没有搞清规则：？
sum_pairs(, 10)
# ^--------^ 5 + 5 = 10, index: 1, 5
# ^-^ 3 + 7 = 10, index: 3, 4 *
#* 虽然整体最早出现的答案
== 冬雪雪冬 发表于 2017-5-11 13:38
没有搞清规则：？
好像打错字了，应该是返回整体最早出现的答案。
简单说，其实就是答案的后一个数字排在前面的优先。 ooxx7788 发表于 2017-5-11 14:00
好像打错字了，应该是返回整体最早出现的答案。
简单说，其实就是答案的后一个数字排在前面的优先。
明白了。
def sum_pairs(list1, num):
for i in range(1, len(list1)):
for j in range(i):
if list1 + list1 == num:
return , list1] 冬雪雪冬 发表于 2017-5-11 14:08
明白了。
从计算角度而言，结果这样肯定是没有问题的。
但是时间上是完成不了的。两层循环肯定超时。 ooxx7788 发表于 2017-5-11 14:32
从计算角度而言，结果这样肯定是没有问题的。
但是时间上是完成不了的。两层循环肯定超时。
这样改，不知效率能否提高。
def sum_pairs(list1, num):
for i in range(1, len(list1)):
if list1[:i].count(num - list1):
return , list1] 本帖最后由 ooxx7788 于 2017-5-11 15:48 编辑
不对不对,原来刚刚是我网络卡了,才通过的!
依然是
Process was terminated. It took longer than 12000ms to complete
但是我觉得你这样好像已经效率很高了!
这些要求时间,和代码长度的题目贼烦. 本帖最后由 ooxx7788 于 2017-5-11 15:54 编辑
冬雪雪冬 发表于 2017-5-11 15:09
这样改，不知效率能否提高。
不过我刚刚偷偷瞄了一眼答案,我就明白了,不是题目设计的问题.
确实是有方法可以提高速度的. ooxx7788 发表于 2017-5-11 15:51
不过我刚刚偷偷瞄了一眼答案,我就明白了,不是题目设计的问题.
确实是有方法可以提高速度的.
没有更好的想法，用set是否快点。
def sum_pairs(list1, num):
for i in range(1, len(list1)):
if num - list1 in set(list1[:i]):
return , list1] 冬雪雪冬 发表于 2017-5-11 16:37
没有更好的想法，用set是否快点。
没错，就是set。
还是要服你，我反正是没想起来。 冬雪雪冬 发表于 2017-5-11 15:09
这样改，不知效率能否提高。
if list1[:i].count(num - list1)
请问这一句怎么解释啊，求教 badaoqingchen 发表于 2017-5-11 16:53
if list1[:i].count(num - list1)
请问这一句怎么解释啊，求教
这是看num - list1的值是否在list1[:i]中，如果不在返回0
为什么是list1[:i]呢？假如第一个数在列表的第5位，只看0~4位就可以了。 ooxx7788 发表于 2017-5-11 16:43
没错，就是set。
还是要服你，我反正是没想起来。
我不知道是题目哪个网站的，请帮我测试一下，看看速度。 冬雪雪冬 发表于 2017-5-11 16:58
这是看num - list1的值是否在list1[:i]中，如果不在返回0
为什么是list1[:i]呢？假如第一个数在列表的第 ...
水土都不服，就服你{:10_277:}
明白了，这个是判断count( )的返回值。
我感觉for循环已经挺快的了啊，为什么用count（） 和 set（）会更快呢？
内部判断的时候，不管set还是count不应该都是用for循环遍历吗 badaoqingchen 发表于 2017-5-11 17:06
水土都不服，就服你
明白了，这个是判断count( )的返回值。
我感觉for循环已经挺快的了啊， ...
我不是很能理解其中的原因，一般教科书上说，集合是hash散列，查找的速度原快于列表元组，特别是数据量大时。 冬雪雪冬 发表于 2017-5-11 16:59
我不知道是题目哪个网站的，请帮我测试一下，看看速度。
还是不行，超时。
这是codewars5kyu的题目, 这个级别的题目会出现对时间或代码量的限制性要求.
单论逻辑而言, 这个题目本身到也不难.
原文地址:
https://www.codewars.com/kata/sum-of-pairs/train/python ooxx7788 发表于 2017-5-11 17:10
还是不行，超时。
这是codewars5kyu的题目, 这个级别的题目会出现对时间或代码量的限制性要求.
单论 ...
我再想想，看看还有什么办法。 冬雪雪冬 发表于 2017-5-11 16:37
没有更好的想法，用set是否快点。
还有set()这种函数{:10_256:}学习了