关于Euler问题#8的效率
我正在做Euler项目问题#8：
最大乘积的1000位数中的四个相邻数字为9×9×8×9= 5832。73167176531330624919225119674426574742355349194934 96983520312774506326239578318016984801869478851843 85861560789112949495459501737958331952853208805511 12540698747158523863050715693290963295227443043557 66896648950445244523161731856403098711121722383113 62229893423380308135336276614282806444486645238749 30358907296290491560440772390713810515859307960866 70172427121883998797908792274921901699720888093776 65727333001053367881220235421809751254540594752243 52584907711670556013604839586446706324415722155397 53697817977846174064955149290862569321978468622482 83972241375657056057490261407972968652414535100474 82166370484403199890008895243450658541227588666881 16427171479924442928230863465674813919123162824586 17866458359124566529476545682848912883142607690042 24219022671055626321111109370544217506941658960408 07198403850962455444362981230987879927244284909188 84580156166097919133875499200524063689912560717606 05886116467109405077541002256983155200055935729725 71636269561882670428252483600823257530420752963450在拥有最大产品的1000位数字中找到13个相邻的数字.这种产品的价值是多少？
下面是我对这个问题的代码：
L = []
L.append("73167176531330624919225119674426574742355349194934")
L.append("96983520312774506326239578318016984801869478851843")
L.append("85861560789112949495459501737958331952853208805511")
L.append("12540698747158523863050715693290963295227443043557")
L.append("66896648950445244523161731856403098711121722383113")
L.append("62229893423380308135336276614282806444486645238749")
L.append("30358907296290491560440772390713810515859307960866")
L.append("70172427121883998797908792274921901699720888093776")
L.append("65727333001053367881220235421809751254540594752243")
L.append("52584907711670556013604839586446706324415722155397")
L.append("53697817977846174064955149290862569321978468622482")
L.append("83972241375657056057490261407972968652414535100474")
L.append("82166370484403199890008895243450658541227588666881")
L.append("16427171479924442928230863465674813919123162824586")
L.append("17866458359124566529476545682848912883142607690042")
L.append("24219022671055626321111109370544217506941658960408")
L.append("07198403850962455444362981230987879927244284909188")
L.append("84580156166097919133875499200524063689912560717606")
L.append("05886116467109405077541002256983155200055935729725")
L.append("71636269561882670428252483600823257530420752963450")
M = []
for s in L:
for i in list(s): M.append(i)
greatest_product = 0
for i in range(len(M)):
product = 1
substring = M[i:i+13]
for digit in substring:
product*=int(digit)
if product > greatest_product:
greatest_product = product
print greatest_product代码可以工作，但是如何提高效率呢？
回答 2
Code Review用户
发布于 2014-07-30 17:38:06
- 循环遍历整个
range(len(M))。这意味着，最后几个产品的锻炼不到13位数。在这个特殊的例子中，这并不重要(反正它们都是零)，但是在一般情况下可能会导致错误的结果。在range(len(M) - 13)上迭代。 - 数字到整数的转换对每个数字发生13次.在进行计算之前，最好在单独的循环中转换它们一次。
- 每次遇到0时，您都可以安全地跳过整串数字:无论如何，产品都是0。
- 滑动窗口技术可能会有所帮助。
伪码：
product *= data[head]
product /= data[tail]
head += 1
tail += 1(小心不要除以0)。
Code Review用户
发布于 2015-08-13 06:18:39
由于问题是关于提高效率，我想指出，搜索可以限制在较小的字符串。
正如人们所指出的，0总是会产生0的乘积。记住这一点，您可以看到只需要在零之间搜索字符串。
按照这一思路，进一步的优化是自然而然的：
- 只有超过13位数的字符串才能应用。
- 由于这些字符串不再包含零，@vnp建议的滑动窗口将在不检查0的情况下工作。
https://codereview.stackexchange.com/questions/58535
复制相似问题
腾讯云开发者
