计算数字出现次数

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

输入:

44 497

输出:

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可能是特殊情况)中有多少会出现在某个范围内.您无需实际查看每个号码.