42. 整数中1出现的次数

• 将一个数字中1出现的次数拆成个、十、百位中1出现次数的和
  以321为例：

1. cnt = 32 + 1，把321拆成高位32和1，固定个位是1，高位的取值可以是0~31共32个数，由于低位为1大于0，所以高位还可以取32（即数字321），则个位上1出现的次数是32+1=33
2. cnt = 30 + 10，把321拆成高位3和21，固定十位是1，高位可以取 0 ~ 2 共30个数，由于低位是21-10+1大于0，所以高位还可以取3（即数字310~319），则十位上1出现的次数是30 + 10 = 40
3. cnt = 0 + 100，把321拆成高位0和321，固定百位是1，高位可以取 0 个数，由于低位是321-100+1大于0，所以可以取数字100~199），则百位上1出现的次数是0 + 100 = 100

所以321中1出现的次数是173

class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        cnt, i = 0, 1
        while i <= n: # i 依次个十百位的算，直到大于 n 为止。
            cnt += n // (i * 10) * i + min(max(n % (i * 10) - i + 1, 0), i)
            i *= 10
        return cnt