2006-09-16

一道据说是Google的面试题

一道据说是Google的面试题
题目:有一个整数n,写一个函数f(n),返回0到n之间出现的"1"的个数。比如f(13)=6 ; f(11)=4,算出f(n)=n的n(如f(1)=1)？
我用python写了一份代码,还改写了一份c++代码

python源代码
def count(i):
"""count form 0 to this number contain how many 1
1.you shoul know pow(10,n)-1 contain 1 number is n*pow(10,n-1)
2.use 32123 for example:
from 10000 to 32123 the first digit contain 1 number is 1(0000-9999) = pow(10,4) ,
and from 10000 to 30000 the rest digit contain 1 number is ( firstDigit*4*pow(10,4-1) )
so count(32123)=pow(10,4)+( firstDigit*4*pow(10,4-1) ) + count(2123)

print count(1599985)
1599985

print count(8)
1
"""
if i==0:
return 0
if 9>=i>=1:
return 1
digit=len(str(i))
firstDigit=int(str(i)[0])
if firstDigit>1:
now=pow(10,digit-1)
else:
now=int(str(i)[1:])+1
now+=(digit-1)*pow(10,digit-2) * firstDigit
return now+count(int(str(i)[1:]))

def little(i):
count_i=count(i)

if i
 
评论
发表评论

您还没有登录，请登录后发表评论