题目:
给定一个整数 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+920=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