对于整数x,x % (10 ** 9 + 7)
并且x % (1e9 + 7)
都给人一种几次迭代后不同的结果。为了重现这个结果,我分享了我的LeetCode #576解决方案。越界路径。如果我更改return ans % (10 ** 9 + 7)
为return ans % (1e9 + 7)
(意识到这花了我一个小时),我的解决方案将不会通过 94 个测试用例中的 5 个。
请注意,此解决方案比此处某个天才家伙提出的单行解决方案要长得多。然而,同样的问题,他的解决方案出现,如果我们改变% (10 ** 9 + 7)
对% (1e9 + 7)
。
我玩了一下 python 编译器,注意到 1e9 给出了一个浮点文字。所以在我看来,这种特性是由浮点运算的“怪异”引起的。但我仍然不明白小数点后的零如何导致差异。为什么会出现这种差异?
无需复制,可以在此处找到差异:https : //www.diffchecker.com/PyKQCElB
要重现,这是我的解决方案:
class Solution:
def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
if maxMove == 0:
return 0
current_state = [[0 for _ in range(n)] for _ in range(m)]
next_state = [[0 for _ in range(n)] for _ in range(m)]
current_state[startRow][startColumn] = 1
ans = self.count_ways(m, n, current_state)
k = 1
while k < maxMove:
# print("CS:", current_state)
for i in range(m):
for j in range(n):
next_state[i][j] = 0
if i != 0:
next_state[i][j] += current_state[i-1][j]
if i!= m-1:
next_state[i][j] += current_state[i+1][j]
if j != 0:
next_state[i][j] += current_state[i][j-1]
if j != n-1:
next_state[i][j] += current_state[i][j+1]
current_state, next_state = next_state, current_state
ans += self.count_ways(m, n, current_state)
# print("NS:", current_state)
# print("k:{},ans:{}".format(k, int(ans % 10 ** 9 + 7)))
# print("k:{},ans:{}".format(k, int(ans % 1e9 + 7)))
k += 1
# return ans % (1e9 + 7) # This is giving incorrect results.
return ans % (10 ** 9 + 7) # This works fine.
def count_ways(self, m, n, grid):
ways = 0
for i in range(m):
for j in [0, n-1]: # Checking left and right strips of a grid.
ways += grid[i][j]
for j in range(n):
for i in [0, m-1]: # Checking top and bottom strips of a grid.
ways += grid[i][j]
# This will automatically add corner boxes twice.
return ways
编辑:使用此测试用例(参数为findPaths
,按顺序):
36
5
50
15
3
但我仍然不明白小数点后的零如何导致差异。
小数点在哪里不重要。它在漂浮!
为什么会出现这种差异?
因为 Python 中的浮点数是通常的硬件数,这意味着它们的存储和精度有限:
>>> int(123123123123123123123.0)
123123123123123126272
# ^^^^ different!
但是 Python 中的整数具有无限的存储空间和精度(“bignum”):
>>> int(123123123123123123123)
123123123123123123123
所以:
>>> 123123123123123123123 % 10**9
123123123
>>> 123123123123123123123 % 1e9
123126272.0
在第二种情况下,双方都转换为浮点数,因为其中之一是。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句