统计某个给定范围[L,R]内的所有整数中,数字9出席的次数,比如给定范围[88,99]中9出现12次
时间: 2024-01-12 18:05:48 浏览: 13
好的,这是一个数学问题。我们可以把[L,R]内的每个整数都拆分成十进制数位,然后统计数字9出现的次数。
具体来说,我们可以分别计算个位、十位、百位等每个数位上数字9出现的次数,然后把它们加起来就是答案。对于每个数位,我们可以分别计算它对答案的贡献。假设当前考虑的是第i位(从右往左数第i位),那么:
1. 如果R的第i位小于9,那么[L,R]范围内所有数的第i位上数字9出现的次数都不会超过L的第i位上数字9出现的次数。因为[L,R]范围内的所有数的第i位上的数字都不会超过R的第i位,而R的第i位小于9,所以L的第i位上数字9出现的次数必然不少于[L,R]范围内所有数的第i位上数字9出现的次数。因此,我们只需要计算L的第i位上数字9出现的次数即可。
2. 如果R的第i位等于9,那么[L,R]范围内所有数的第i位上数字9出现的次数就等于L的第i位上数字9出现的次数加上1,因为[L,R]范围内恰好有一个数的第i位是9。
3. 如果R的第i位大于9,那么[L,R]范围内所有数的第i位上数字9出现的次数就等于L的第i位上数字9出现的次数加上(R的第i位-9)加上9出现的“额外”次数。其中,9出现的“额外”次数是指[L,R]范围内所有数的第i位上数字从0到R的第i位-1的所有数位上数字9出现的总次数。这个可以递归计算得到,具体做法就是把[L,R]范围内的数按第i位分成两部分:第一部分是第i位等于R的第i位的数,第二部分是第i位小于R的第i位的数。第一部分中恰好有R的第i位-9个数的第i位上是9,因此9出现的“额外”次数就是(R的第i位-9)*(10^(i-1))。对于第二部分,我们可以递归计算出它们的9出现的“额外”次数,然后把它们加起来即可。
最后,把每个数位的贡献加起来,就是[L,R]范围内数字9出现的总次数了。
阅读全文