整数中出现1的次数

数字从小到大，把每个数包含的1的个数放到一个字典里去。
每一个大数分解成最高位+余下数，比如2021分解为2和021两部分，分别判断最高位和分出来的那部分相加即可，缺点是比较费空间

# -*- coding:utf-8 -*-
import collections
class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        sum = 0
        numLib = {}
        N = 1
        for num in range(n+1):
            numLib.setdefault(num,0)
            numLib[num]=(numLib[num % N]+int(num//N==1))
            sum+=numLib[num]
            if num==10*N-1:
                N*=10
        return sum