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

发表于 更新于

关于 计算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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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的个数