"""
思路：应该存储每个位数1出现的次数，eg.一个数为abcdef，那么c位置出现1的次数情况如下：
(1):高位从00~ab-1，则个数应该是ab*1000,因为def可以是任意的千数;
(2):只考虑低位，又分为三种子情况：
1)c=0,则出现1的个数为0
2)c=1,则从000~def的任意数都可以，个数为def+1
3)c>1,则def可以是任意的千数，个数为1000

"""
class Solution(object):
    def numberOf1Between1AndN_Solution(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n==0:#边界情况
            return 0
        digit=[]
        while n:#把每个位数取出来，存入digit
            digit.append(n%10)
            n//=10
        digit=digit[::-1]#从高位到低位存储
        n=len(digit)
        count=0
        for idx in range(n):#分析每个位上1的个数
            if idx!=0:#如果该位数有高位数，就要把(1)的情况加上
                num=0
                for i in range(idx):
                    num+=digit[i]*pow(10,idx-i-1)
                count+=num*pow(10,n-idx-1)
            if digit[idx]==0:#(2)中的1)的情况加上
                count+=0
            if digit[idx]==1:#(2)中的2)的情况加上
                temp=digit[idx+1:]
                num=1
                for i in range(len(temp)):
                    num+=temp[i]*pow(10,len(temp)-i-1)
                count+=num
            if digit[idx]>1:##(2)中的3)的情况加上
                count+=pow(10,n-idx-1)
        return count