整数中出现1的次数
整数中1出现的次数（从1到n整数中1出现的次数）
http://www.nowcoder.com/questionTerminal/bd7f978302044eee894445e244c7eee6
数字从小到大，把每个数包含的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
