思路

统计数字的每一位上出现了多少次1。

难点

仔细的分析每一种情况

具体方法

将数字n表示成 <a>b<c>：由0位开始自右向左第i位数字为b，其代表的数值为$b*10^i$，第i位左边数字的数值为a，第i位右边数字的数值为c（最高位则左边a=0，最低位则右边c=0)

则第i位上出现1的次数为：
1. b==0, 则第i位上取1时，i左边的取值范围为 $1\sim a$，右边的取值范围为$0 \sim 10^i - 1$，总次数为 $a * 10^i$ ;
2. b == 1，则第i位上取1时，i左边的取值范围为 $0\sim a$，右边的取值范围为$0 \sim c$，总次数为 $(a + 1) * c$ ;
3. b > 1，则第i位上取1时，i左边的取值范围为 $0\sim a$，右边的取值范围为$0 \sim 10^i - 1$，总次数为 $(a + 1) * 10^i$ ;

代码

class Solution(object):
    def numberOf1Between1AndN_Solution(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n < 1: return 0
        res = 0
        acc = 0
        c = 0
        vb = 1
        while n > 0:
            b = n % 10
            a = n // 10
            if b == 0:
                if a > 0:
                    acc =  a  * vb
            elif b == 1:
                acc = (a + 1) * (c + 1)
            elif b > 1:
                acc = (a + 1) * vb 

            n //= 10
            res += acc 
            c = b * vb + c
            vb *= 10
            # print(a, b, c, res, acc)
        return res