剑指Offer 43：1~n整数中1出现的次数

Leetcode 233. Number of Digit One

最简单的暴力法，按下表不谈。
使用数学规律来解，用到了递归的想法，将高位数字挨个剥离，进行递归。

举例来说： n = 12345，考虑分解为12345-2346,1-2345两个部分。前面的部分中万位数字为1的个数为2346个，其他四个数位的1个数为，即挑选1个数位为1，其他三个位置任意。
从而将数字通过，降为的运算。代码如下：

class Solution:
    def countDigitOne(self, n: int) -> int:
        import math
        
        
        if n < 1:
            return 0
        elif n < 10:
            return 1
        num = 0
        d = int(math.log10(n))
        z = math.pow(10, d)
        x = n // z
        y = n % z
        if x == 1:
            num += y + 1
        else:
            num += z
        return int(num + x * d * math.pow(10, d - 1) + self.countDigitOne(y))