1～n 整数中 d 出现的次数

这是一道有趣的算法题，题目见:

233. 数字 1 的个数

剑指 Offer 43. 1～n 整数中 1 出现的次数

面试题 17.06. 2出现的次数

居然在三题中出现，确实是很有意思！

思路

根据n每一位的数字分治，举个例子
n = 12345
个位，factor=1时, high=1234，current=5, low=0
十位，factor=10时, high=123，current=4, low=5
百位，factor=100时, high=12，current=3, low=45
...

• 先考虑右边低位

当current小于d时，左边低位无论怎么折腾，current所在位都不会贡献任何一次数字d，所以贡献0次
当current等于d时，固定current所在位为d，左边低位从0到low跑low+1遍，所以贡献low+1次
当current大于d时，固定current为d，左边低位从0到factor-1跑factor遍，所以贡献factor次

• 再考虑右边

对于从1到high的每一个高位数字，current所在位都会出现factor*10次，依次为0123456789，其中只有1次是d，每一个高位数字带动current所在位贡献factor次
所以左边累计贡献为固定的：high * factor

class Solution:
    def numberOf2sInRange(self, n: int) -> int:
        return digit_times(n, 2)

def digit_times(x, d):
    """ 0 <= d, current <= 9 """
    ans = 0
    factor = 1
    while x >= factor:
        high = x // (factor*10)  # 左边高位
        current = (x % (factor * 10)) // factor
        low = x % factor  # 右边低位
        # factor位是d的数字个数
        if current < d:
            ans += high * factor
        elif current == d:
            ans += high * factor + low + 1
        else:  # current > d
            ans += high * factor + factor
        factor *= 10
    return ans