-3

我在一个技能测试系统中发现了下一个编程问题：

给出一个正整数 N。考虑数字序列 [0, 1, ..., N]。这些数字的十进制表示中零的总数是多少？

N 可以非常大。因此，它以长度为 L 的非空字符串 S 的形式给出，其中包含 N 的十进制表示。S 不包含前导零。

写一个函数：

int number_of_zeros(char *S); 


int number_of_zeros(const string &S);

即，给定一个字符串 S，它是某个正整数 N 的十进制表示，返回数字 [0, 1, ..., N] 的十进制表示中零的总数。如果结果超过 1,410,000,016，则该函数应返回结果除以 1,410,000,017 的余数。

例如，对于 S="100"，函数应该返回 12，对于 S="219"，它应该返回 42。

假使，假设：

    * L is an integer within the range [1..10,000];
    * string S consists only of digits (0-9);
    * string S contains no leading zeros.

复杂：

    * expected worst-case time complexity is O(L);
    * expected worst-case space complexity is O(L) (not counting the storage required for input arguments).

我试图解决它并编写函数，但在我的解决方案中运行时间复杂度比 O(L) 更复杂，任何人都可以解决它（至少提供算法或伪代码或解释）？

好成功！

4

2 回答 2

2

这个问题是递归优势的一个很好的例子。考虑简单的基本情况：从 1 到 1 的数字正好有 0 个零。

当您在从 1 到 N（例如 x）的数字中有零个数时，您可以将 1 到 N*10 的数字计算为 9*x+log10(N*10)。论据很简单：您需要九个块，其中数字 1...、2...、3... 的零个数相等，而数字 N*10 写为 10000... 。

这种递归对所有 10 的幂都有效。当您将数字拆分为构成它的 10 的幂时，任意 N 的递归并不难计算。

于 2011-11-08T13:05:14.497 回答
0

由于只有 10000 的上限，从技术上讲，这是一个降低时空复杂性的竞赛，只需预先计算提交代码中的所有可能答案。您可能会注意到这是非常低效的内存，但观察到永远不会出现任何查找值距离“零”超过 9 个数字的情况，您可以使用字典来节省大量内存。

zeros.py（生成实际代码，尽管在 L 上是线性时间）：

def zeros(n):
        l = str(n)
        return l.count("0")

total = 0
d = {}
for i in xrange(10001):
        delta =  zeros(i)
        if (delta>0):
                total += delta
                d[i] = total

print len(d)
print
print "d = " + str(d)
print "N = int( raw_input () )"
print "while (N not in d):"
print "\t N-=1"
print "print d[N]"

生成这个（32kb）文件（31ms）：http ://paste.pocoo.org/show/504589/

运行时 ~ 摊销 O(1)

空间 ~ L=[0..10000] 的零点密度为 2621 ~ 26.21%。我不认为零的分布会大大增加，但无论如何 - 它的密度肯定受 O(L) 的限制。

于 2011-11-08T13:58:57.593 回答