计算数字出现 [英] Counting digit occurrences
问题描述
这个问题真的使我感到困惑；我们给了两个整数 A ， B ，我们要计算出现在 [A，B] 范围内的数字.我可以说，如果我们可以计算在 [0，A] 和 [0，B] 范围内的数字出现次数，那么其余的就不那么重要了.那么，如何计算在 [0，x] 范围内的数字出现次数呢? 这不是功课，这实际上是SPOJ的问题. 天真的方法行不通，因为A和B可能高达10 ^9.下面是一些示例:
This problem is really confusing me; we're given two integers A, B, we want to count occurrences of digits in the range [A, B]. I though that if we could count the number of digit occurrences in the range [0, A] and [0, B], then the rest is trivial. So how can I count digit occurrences in a range [0, x]? This isn't homework, this is actually a problem from SPOJ. The naive approach won't work, as A and B can be as large as 10 ^ 9. Here are some examples:
输入:
1 10
输出:
1 2 1 1 1 1 1 1 1 1
1 2 1 1 1 1 1 1 1 1
输入:
44 497
输出:
85 185 185 185 190 96 96 96 95 93
85 185 185 185 190 96 96 96 95 93
推荐答案
我将首先尝试使用蛮力方法来使某些东西起作用.查看每个数字，遍历该数字的字符串表示形式中的每个字符，等等.
I would try the brute force approach first to get something working. Look at each number, iterate through each character in the string representation of that number, etc.
但是，有一种更简单的方法.
However, there is an easier way.
- 在间隔[0,9]中，出现3次1次
- 在时间间隔[0,99]中，第3位出现10次，第二位出现10次
- 在时间间隔[0,999]中，第3位出现100次，第二位出现100次，第3位出现100次.
您可以对此进行一般化，并花一点力气得出一个公式，该公式确定某个数字(在0可能是一种特殊情况)在一定范围内出现的次数.您实际上不需要仔细检查每个数字.
You can generalize this and with a bit of effort come up with a formula for how many of a certain digit (0 being a possible special case) will appear in a certain range. You don't need to actually go through each number.
这篇关于计算数字出现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
