时间戳

首页 > 解决方案 > sum中遇到整数溢出

python - sum中遇到整数溢出

问题描述

我的印象是 python 整数是任意精度。但是今天在解决一个 leetCode 问题，以及多次提交错误答案时，我终于添加 mod到我的解决方案中并且它起作用了。我对它发生的原因感到困惑，以下是我的代码：

import math

class Solution:
    def numRollsToTarget(self, d: int, f: int, target: int) -> int:
        if target>d*f or target<d:
            return 0
        memo = {}
        return int(self.recurse(d,f,target,memo)%(math.pow(10,9) + 7))

    # def recurse(self,d,f,target,memo):

    def recurse(self,d,f,target,memo):
        key = "%d %d"%(d,target)
        if key in memo:
            return memo[key]
        if d*f<target or target<d:
            return 0
        elif d==1:
            return 1
        else:
            ways = 0
            for i in range(1,f+1):
                # following line uncommented, and the next one commented, gives correct answer
                #ways = (ways+self.recurse(d-1,f,target-i,memo))%(math.pow(10,9) + 7)
                ways += self.recurse(d-1,f,target-i,memo)

            memo[key] = ways
            return memo[key]

我的猜测是溢出导致了错误的结果，每次求和时都修改部分结果可以解决问题。还是我还缺少其他东西？

标签： pythonpython-3.xinteger-overflow

解决方案

您正在使用浮点数进行计算：

return int(self.recurse(d,f,target,memo)%(math.pow(10,9) + 7))

这会强制使用浮点数计算模数，这不是整数溢出，而是浮点数不准确导致您得出错误的结果。

让我们做d, f, target = 30, 30, 500。然后int(self.recurse(d, f, target, memo)返回1319186227454333254490768998141738589030871，int一会儿math.pow(10, 9) + 7是1000000007.0，一float。

所以这就是你正在做的事情：

print(1319186227454333254490768998141738589030871 % 1000000007.0)  # wrong
811448245.0

如果您改为确保被除数也是整数（10 ** 9 + 7或1000000007）：

print(1319186227454333254490768998141738589030871 % 1000000007)  # right   
222616187

推荐阅读