这个问题真让我困惑;给定两个整数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
最佳答案
我会先尝试蛮力方法来使某些东西起作用。查看每个数字,遍历该数字的字符串表示形式中的每个字符,等等。
不过,还有一个更简单的方法。
- 在区间[0,9]中,3出现1次
- 在区间[0,99]中,3在第一位出现10次,在第二位出现10次
- 在区间[0,999]中,3在第一位出现100次,在第二位出现100次,在第三位出现100次。
您可以对此进行概括,并通过一些努力得出一个公式,用于确定某个数字(0 是一种可能的特殊情况)中有多少会出现在某个范围内。您不需要实际检查每个数字。
关于algorithm - 计算数字出现次数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6630139/