233.数字1的个数

题目:
给定一个整数 n,计算所有小于等于 n 的非负整数中数字 1 出现的个数。

示例:

输入: 13
输出: 6
解释: 数字 1 出现在以下数字中: 1, 10, 11, 12, 13 。

思路:
这题可以看出一个规律
1位数就是1-9只有一个1
2位数就是10-99除了10-19有10个1,20-99有91个1,总共就是19个1
3位数就是100-999,就算是100+9
20=280个
所以f(n)=10*f(n-1)+10**(n-1)
那么我们推广到更广的情况下
那么我们关心最高为是k
就有:
1.
个位数k>=1
就是1个1
2.
两位数
if k == 1
n-10+1+1
elif k>=2
10+k-1+1
3.
三位数
if k==1
n-100+1+剩下的二位数
if k>=2
10^2+(k-1)*所有二位数

代码

class Solution:
    def countDigitOne(self, n: 'int') -> 'int':
        if n<=0:
            return 0
        p,place,total=n,1,0
        while p>0:
            last=p%10
            p//=10
            total+=p*place
            if last==1:
                total+=n%place+1
            elif last>1:
                total+=place
            place*=10
        return total
上一篇:Python GUI(Tkinter)初探


下一篇:Place the Robots