机试——从1到n正数中1出现的个数

https://blog.csdn.net/yi_afly/article/details/52012593

题目:b求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。

总结各个位上面1出现的次数，我们可以发现如下规律:

• 若weight为0，则1出现次数为round*base
• 若weight为1，则1出现次数为round*base+former+1
• 若weight大于1，则1出现次数为rount*base+base

def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        if n<1:
            return 0
        
        count  = 0
        base = 1     #用来记录每个round中1出现的次数，weight为个位时，base为1，weight为十位时，base为10
        rou = n
        
        while rou>0:
            weight = rou%10    #知识当前最低位的值，依次获得个位数、十位数、百位数
            rou//=10            #获得最低位前面的全部位，也就是round值
            count+=rou*base    #无论weight为任何数，当前位为1的个数都至少为rou*base
            
            #如果weight为1，那么当前位为1的个数前一位的值+1
            if weight==1:
                count += (n%base)+1
            elif weight>1:
                count += base
            
            base*=10
        return count