22_NumberOfBetween1AndN_Solution.py

# 求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）
class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # 循环的出口是 highValue = 0

        # 我们从最低位开始一个位一个位的来寻找 1 的可能出现的 情况次数。

        # 一开始 精准度为1.高位低位中位 先赋值为1.
        preceise = 1
        # 高位数
        highValue = 1
        # 低位数
        lowValue = 1
        # 中位数
        midValue = 1

        # 计数 后面的位数。
        count = 0
        # 计数 1 的次数和
        sumNum = 0
        # 循环的 出口是我们找不到最高位了，那么这个时候就说明，我们遍历到了 这个数字的最高位。
        while highValue != 0:
            # 高位 先将这个数 除以10 得到高位
            highValue = n // (preceise * 10)
            # 中位 先将这个数  与 10 取余。
            midValue = (n // preceise) % 10
            # 低位 先将这个数 除以 1 那么低位就是个位后面的，没有就是0.
            lowValue = n % preceise
            # 每遍历一次 向右移一位，那么就是说 精准度要乘以10.
            preceise *= 10
            # 如果这个数是0 的话，

            if midValue == 0:
                # 那么它就是高位的值，乘以 10^后面的位数 次方，但是这个时候 对于中位 来说 它是个位，后面没有位，所以是0，
                num = (highValue) * pow(10, count)
            # 如果这个数 大于1 的话，
            elif midValue > 1:
                # 那么它 就是 最高位加1 乘以 10^后面的位数 次方，
                num = (highValue + 1) * pow(10, count)
            else:
                # 否则的话 它就是等于1 的情况了，对于等于1 的1情况，又是比较特殊的情况，它需要 最高位 * 它10 的后面位数个数的次方，然后要加上我们低位 的数值再加 1， 原因在上面的分析中已经给出。
                num = highValue * pow(10, count) + (lowValue + 1)
            # 最后 我们1 出现的 次数 就是这 三个 num 的和，。
            sumNum += num
            # 没循环一次，这个三个就往左移一次吗，那么这个时候它们 后面的位数也就会 多一位。
            count += 1
        # 最后返回这个  次数和。
        return sumNum