python - 从[1,2，…num]开始计数0

我们得到一个大的数字'num'，它可以有多达10^4个数字，（num<=10^（10000）），我们需要在从1到'num'的十进制表示中找到零的个数。

eg:
countZeros('9') = 0
countZeros('100') = 11
countZeros('219') = 41

我能想到的唯一办法就是使用暴力，这显然对于大量的输入来说太慢了。
我在this链接中找到了下面的python代码，它在o（l）中执行了所需的操作，l的长度是'num'。

def CountZeros(num):
    Z = 0
    N = 0
    F = 0
    for j in xrange(len(num)):
        F = 10*F + N - Z*(9-int(num[j]))
        if num[j] == '0':
            Z += 1
        N = 10*N + int(num[j])
    return F

我不明白它背后的逻辑。任何帮助都将不胜感激。

最佳答案

from 0 - 9 : 0 zeros
from 10 - 99: 9 zeros ( 10, 20, ... 90)

--100-199 explained-----------------------
100, 101, ..., 109 : 11 zeros (two in 100)
110, 120, ..., 199:  9 zeros (this is just the same as 10-99) This is important
Total: 20
------------------------------------------

100 - 999: 20 * 9 = 180

total up to 999 is: 180 + 9: 189
CountZeros('999') -> 189

继续这个模式，您可能会开始看到整个模式，并最终看到算法。

关于python - 从[1,2，…num]开始计数0，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20614288/