时间戳

首页 > 解决方案 > 如何让这段代码更有效地应对编码挑战？

python - 如何让这段代码更有效地应对编码挑战？

问题描述

我正在做名为 Integers: Recreation One in Codewars 的编码挑战。

挑战 => 给定两个整数 m, n (1 <= m <= n)，我们希望找到 m 和 n 之间的所有整数，其除数平方和本身就是一个平方。

def list_squared(m, n):
    lst = list()
    for num in range(m, n+1):
        total= 0
        for i in range(1, num//2 +1):
            if num % i == 0:
                total += i**2
        total += num**2

        if (total**(1/2)) % 1 == 0:
            lst.append([num, total])

    return lst

我的代码适用于示例测试，但是当我尝试提交它时，它给了我“执行超时”错误。我想我必须使它更有效，但不知道该怎么做。如何让代码更高效？

标签： python

解决方案

一个sqrt想法的实现：

def list_squared(m, n):
    lst = list()
    for num in range(m, n+1):
        total = 0
        sqrt = int(math.sqrt(num))
        for i in range(1, sqrt+1):
            q,r=divmod(num,i)
            if r == 0:
                total += i*i + q*q
        if sqrt*sqrt == num:
            total -= num

        if math.sqrt(total) % 1 == 0:
            lst.append([num, total])

    return lst

它似乎工作。一些可能有意义或可能没有意义的事情：

  • 我不知道是否**(1/2)或math.sqrt性能更好，它可以检查。但是我觉得sqrt更具可读性。当然，如果您不允许使用数学库，请坚持使用**
  • 很可能x*x比 快x**2，也可以检查
  • 在汇编级别，商和余数是在一个步骤中生成的，这对于 Python 可能是正确的，也可能不是。然而，这就是我使用的原因divmod（所以q*q替换(num/i)*(num/i), 或(num/i)**2）

实际上，这些细节可能根本不重要，缩短内部循环应该是主要技巧。

@HEK：您“感觉”可以通过/2事物以某种方式缩短循环，但实际上它必须是平方根。
如果i是 的除数num，num/i也是 的除数num。如果i从 开始增加1，num/i从num/1（所以从num自身）开始减少。随着时间的流逝，他们会在某个地方相遇，那就是sqrt(num)。增加i上面sqrt(num)的结果会检查您已经看到的除数对。以 20 为例：

i   20/i
1   20
2   10
3   <something fraction>
4   5    <--- this is the last step when we encounter a new divisor
5   4    <--- here the divisors are "old", we have seen 4 and 5 already
6   <something fraction>
......

所以除数是 1,20,2,10,4,5 - 我们不必单独检查 5...20，检查 就足够了1...4=(int)sqrt(20)，这是一个很大的收获。

推荐阅读