剑指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))
