algorithm - 计算数字出现次数

Question

这个问题真让我困惑；给定两个整数A、B，我们想计算[A, B]范围内数字的出现次数。我认为如果我们可以计算 [0, A] 和 [0, B] 范围内数字出现的次数，那么剩下的就很简单了。那么如何计算 [0, x] 范围内的数字出现次数？这不是作业，这实际上是 SPOJ 的问题。天真的方法行不通，因为 A 和 B 可以大到 10 ^ 9。下面是一些示例:

输入:

1 10

输出:

1 2 1 1 1 1 1 1 1 1

输入:

44497

输出:

85 185 185 185 190 96 96 96 95 93

Answer 1

我会先尝试蛮力方法来使某些东西起作用。查看每个数字，遍历该数字的字符串表示形式中的每个字符，等等。

不过，还有一个更简单的方法。

• 在区间[0,9]中，3出现1次
• 在区间[0,99]中，3在第一位出现10次，在第二位出现10次
• 在区间[0,999]中，3在第一位出现100次，在第二位出现100次，在第三位出现100次。

您可以对此进行概括，并通过一些努力得出一个公式，用于确定某个数字(0 是一种可能的特殊情况)中有多少会出现在某个范围内。您不需要实际检查每个数字。