题目描述
求出113的整数中1出现的次数,并算出1001300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数。
按位来求
# -*- coding:utf-8 -*-
class Solution:
def NumberOf1Between1AndN_Solution(self, n):
# write code here
def find(n, x):
res = 0
# loop from end to start
for i in range(1, 1+len(str(n))):
hi = n / 10**i # value higher than index i
cur = n % 10**i / 10**(i-1) # current bit
lo = n % 10**i % 10**(i-1) # value lower than index i
if cur==x:
res += hi*10**(i-1) + lo+1
elif cur<x:
res += hi*10**(i-1)
else:
res += (hi+1)*10**(i-1)
return res
return find(n, 1)
