文章/答案/技术大牛

发布

社区首页 >问答首页 >工作2和求解器

问工作2和求解器
EN

Code Review用户

提问于 2020-01-25 17:08:02

回答 3查看 556关注 0票数 5

这是我第一个工作的2和计算器。它通过找到target在s中的差异来确定该2和是否存在。

假设我们的target是-5.我从s中的第一个索引开始，使用减法(-5-(-8) = 3)，结果是3，代码将检查s中的差异。如果列表s中存在差异，则输出是肯定的。

s = [-8,3,5,1,3]
target = -5

for j in range(0, len(s)):
  if target-int(s[j]) in s[j+1:len(s)]:
   print('yes')
   quit()

print('no')

我修正了当int(s[j])等于target-int(s[j])时返回假yes的错误。我是用s[j+1:len(s)]做的，一个例子是我们的target是4，但是我们对S的投入是[2]。它会说是，因为int(s[j])等于target-int(s[j])。

是否可以将这些代码全部写成一两行代码？

python

k-sum

回答 3

Code Review用户

发布于 2020-01-25 19:27:40

将代码直接转换为一行代码：

s = [-8,3,5,1,3]
target = -5

is_2sum = any(target - s[j] in s[j+1:len(s)] for j in range(len(s)))
print(is_2sum)

几个注意事项：

循环现在被转换成一个生成器表达式:我们记录列表的其余部分中是否存在每个差异，并将其与any结合起来，后者将检查结果列表是否包含True。
特别要注意的是，在调用any时，我们不通过列表理解来构造列表。实际上，通过使用生成器表达式，我们允许在找到True值时尽早退出，这可能会大大加快对正实例的执行。
你的方法在二次时间内运行。但是，该算法可以进一步优化以在线性时间内运行(例如，类似于CS.SE的问题)。

如果你对二次时间算法很满意，另一种选择是用暴力强迫每对.将这种算法推广到k-和也是很简单的.所以，为了好玩，我们也可以：

from itertools import combinations 

s = [-8,3,5,1,3]
target = -5

is_2sum = any(sum(p) == target for p in combinations(s, 2))
print(is_2sum)

如前所述，这不是高度可伸缩的，但对于初学者来说，阅读和理解应该非常容易(如果这很重要的话)。

票数 6

Code Review用户

发布于 2020-01-25 19:35:45

你应该把这当成一种功能。
您应该使用4个空格进行缩进。
如果s成为字典中的数字计数，那么in将在O(1)时间执行，其中列表在O(n)时间中执行。
使用quit并不是真正的惯用，它的添加是为了使退出REPL变得更容易。
而不是for j in range(0, len(s))，您可以使用for item in s。
使用更好的变量名，s和j就是meh。
你可以用一个理解，用any来减少噪音。

import collections


def has_two_sum(items, target):
    items = collections.Counter(map(int, items))
    for item in map(int, items):
        remainder = target - item
        if items.get(remainder, 0) >= (2 if item == remainder else 1):
            return True
    return False


if has_two_sum(s, target):
    print('yes')
else:
    print('no')

或者你可以把它写在这一行上，看起来就像垃圾：

s=collections.Counter(map(int,s));print(['no','yes'][any(map(lambda i:s.get(t-i,0)>=1+(i==t-i),s))])
f=set();print(['no','yes'][any(map(lambda i:(t-i in f,f.add(i))[0],s))])

票数 4

Code Review用户

发布于 2020-01-28 01:58:34

我相信这会解决你的问题：

# Using ternary operator to condense the print's
two_sum = lambda s, target: print('yes') if any(map(lambda x: target-x in s and s.count(x)>1, s)) else print('no')

# If s.count(x) is 1, it means the subtraction resulted in the same element took that time for the operation, which we don't want to happen. So the count must be greater then 1

two_sum([-8, 3, 5, 1, 3], -5)
# Output is "yes"

two_sum([2], 4)
# Output is "no"

因此，我们将函数包装在lambda中，在map调用中使用另一个lambda，并保留列表中的所有项，检查输出是否与用于计算的另一个元素匹配。

基准

我想知道@Juho的回答是否提供了一个更快的功能，所以我对两者都进行了基准测试。

所以：

two_sum = lambda s, target: any(map(lambda x: target-x in s and s.count(x)>1, s))

is_2sum = lambda s, target: any(target - s[j] in s[j+1:len(s)] for j in range(len(s)))

# The print's aren't necessary for the benchmark.

然后，我在Google上运行了以下代码：

two_sum = lambda s, target: any(map(lambda x: target-x in s and s.count(x)>1, s))

is_2sum = lambda s, target: any(target - s[j] in s[j+1:len(s)] for j in range(len(s)))

test_function = two_sum
# test_function = is_2sum

if __name__ == "__main__":
    import timeit
    setup = "from __main__ import test_function"
    average=0
    for i in range(0,100):
      average=average+timeit.timeit("test_function([-8, 3, 1, 5, 1, 3], -5)", setup=setup, number=1000000)
    print(average/100)

方法timeit.timeit()将运行每个函数1.000.000次，然后记录100个迭代的输出(因此，我们实际运行函数100.000.000次)并取平均值。

结果：

对于函数two_sum：

第一轮：0.9409843384699957

第二轮：0.948360692339993

对于函数is_2sum：

第一轮：0.9963176720300112

第二轮：0.998327726480004

正如您所看到的，two_sum函数的性能有了提高，这是否来自于使用map()和避免列表操作，我不知道，但速度要快一些。

票数 1

页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://codereview.stackexchange.com/questions/236165

复制

相似问题

问工作2和求解器
EN

回答 3

Code Review用户

Code Review用户

Code Review用户

基准

结果：

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问工作2和求解器EN

回答 3

Code Review用户

Code Review用户

Code Review用户

基准

结果：

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问工作2和求解器
EN