计算1-866278171中奇数列中3出现的个数

2023-07-16

关于 计算1至N中X出现的个数

编程之美上给出的规律:
1.如果第i位(自右至左,从1开始标号)上的数字为0,则第i位可能出现1的次数由更高位决定(若没有高位,视高位为0),等于更高位数字X当前位数的权重10^(i-1)。
2.如果第i位上的数字为1,则第i位上可能出现1的次数不仅受更高位影响,还受低位影响(若没有低位,视低位为0),等于更高位数字X当前位数的权重10^(i-1)+(低位数字+1)。
3.如果第i位上的数字大于1,则第i位上可能出现1的次数仅由更高位决定(若没有高位,视高位为0),等于(更高位数字+1)X当前位数的权重10^(i-1)。

通用结论:

  1. 从 1 至 10,在它们的个位数中,任意的 X 都出现了 1 次
  2. 从 1 至 100,在它们的十位数中,任意的 X 都出现了 10 次
  3. 从 1 至 1000,在它们的千位数中,任意的 X 都出现了 100 次
  4. 依此类推,从 1 至 10^i,在它们的左数第二位(右数第 i 位)中,任意的 X 都出现了10^(i−1) 次

得出的算法如下:

当计算右数第 i 位包含的 X 的个数时:

  1. 取第 i 位左边(高位)的数字,乘以 10^(i−1),得到基础值 a

  2. 取第 i 位数字,计算修正值:

    1. 如果大于 X,则结果为 a+10^(i−1)
    2. 如果小于 X,则结果为 a
    3. 如果等 X,则取第 i 位右边(低位)数字,设为 b,最后结果为 a+b+1
def count_x_between_one_and_n(n,x):
    if n < 0 or x < 1 or x > 9:
        return 0
    high,low,current,tmp,i = 1,1,1,1,1
    high = n
    total = 0
    while high !=0:
        high = int(n/int(math.pow(10,i)))
        tmp = int(n%int(math.pow(10,i)))
        current = int(tmp/int(math.pow(10,i-1)))
        low = int(tmp%int(math.pow(10,i-1)))
        if current == x:
            total += high*int(math.pow(10,i-1))+low+1
        elif current < x:
            total += high*int(math.pow(10,i-1))
        else:
            total += (high+1)*int(math.pow(10, i-1))
        i+=1
    return total

res =count_x_between_one_and_n(866278171,3)) # 796741437
# 求为奇数的时候,当个位为3的时候,均为奇数,除去这一部分,这剩下的
# 奇偶数各占一半
a = 796741437 # 总个数
b = 866278170/10 # 个位为 3 的个数
c = (a - b)/2 + b # 再加上个位为3的个数,得出奇数列中3出现的个数 441684627

结尾

Leetcode 也有类似的题目是求 1 出现的个数,相对比较简单一些,有兴趣可以尝试一下 数字1的个数