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

输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。

例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

示例 1：

输入：n = 12
输出：5

示例 2：

输入：n = 13
输出：6

限制：

• 1 <= n < 2^31

Python 解答：
1.暴力超时

class Solution:
    def countDigitOne(self, n: int) -> int:
        def count(n):
            c = 0
            while n > 0:
                n, r = divmod(n, 10)
                if r == 1:
                    c += 1
            return c 
        total = 0
        for i in range(1, n+1):
            total += count(i)
        return total

2.找规律

class Solution:
    def countDigitOne(self, n: int) -> int:
        if n == 0:
            return 0
        elif n <= 9:
            return 1
        m = n
        base = 1
        while m >= 10:
            m //= 10
            base *= 10
        l = n - base*m
        if m == 1:
            return self.countDigitOne(l) + self.countDigitOne(base-1) + 1 + l
        else:
            return self.countDigitOne(l) + m*self.countDigitOne(base-1) + base