Re: Re:答复: [cpp] 一道据说是Google的面试题
李创
converse_lc at 163.com
Tue Sep 19 21:11:06 CST 2006
没有仔细看各位的回复,在别的论坛抄来的答案,速度很快的说:
long long f(long long n)
{
int k;
long long e, m = n, r;
if(n <= 1) return n;
for(k=0, e=1; m >= 10; k++, e *= 10) m /= 10;
r = n - m*e;
if(m == 1)
return(e/10*k+r+1+f(r));
else
return(e/10*k*m+e+f(r));
}
int digit_num(long long n)
{
int k;
for(k=0; n > 0; k++) n /= 10;
return k;
}
int main()
{
int k;
long long n, v;
for(n = 1; n<10000000000;)
{
v = f(n);
if(v == n) {
printf("%lld\n", n);
n++;
}
else if(v > n) n = v;
else {
k = digit_num(n + n - v);
n += (n-v)/k + 1;
}
}
}
======= 2006-09-18 23:04:26 您在来信中写道：=======
>我的算法
>#一道据说是Google的面试题
>#题目:有一个整数n,写一个函数f(n),返回0到n之间出现的"1"的个数。比如f(13)=
>6 ; f(11)=4,算出f(n)=n的n(如f(1)=1)？
>
>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<count_i:
>
>#i reduce 1 , count_i at most reduce 9 , so you at least reduce
>(count_i-i)/(9-1) to reach i==count_i
>if (count_i-i)/8>1:
>return i-(count_i-i)/8
>
>if i>count_i:
>#i reduce 1 , count_i at least reduce 0 , so you at least reduce
>(i-count_i) to reach i==count_i
>return count_i
>
>return i-1
>
>def run(i=10*10**(10-1)):
>while i>0:
># print i,'=>i-count_i= ',i-count(i)
>if i==count(i):
>print i,','
>
>i=little(i)
>
>def fastrun(t=10*10**(10-1)):
>"""This just list out all this king of element :) But it is fastest and
>most useful"""
>all=[1, 199981, 199982, 199983, 199984, 199985, 199986, 199987, 199988,
>199989, 199990, 200000, 200001, 1599981, 1599982, 1599983, 1599984,
>1599985, 1599986, 1599987, 1599988, 1599989, 1599990, 2600000, 2600001,
>13199998, 35000000, 35000001, 35199981, 35199982, 35199983, 35199984,
>35199985, 35199986, 35199987, 35199988, 35199989, 35199990, 35200000,
>35200001, 117463825, 500000000, 500000001, 500199981, 500199982,
>500199983, 500199984, 500199985, 500199986, 500199987, 500199988,
>500199989, 500199990, 500200000, 500200001, 501599981, 501599982,
>501599983, 501599984, 501599985, 501599986, 501599987, 501599988,
>501599989, 501599990, 502600000, 502600001, 513199998, 535000000,
>535000001, 535199981, 535199982, 535199983, 535199984, 535199985,
>535199986, 535199987, 535199988, 535199989, 535199990, 535200000,
>535200001, 1111111110]
>for i in all:
>if(t>=i):
>print i
>
>print "first test with run() to:111111111"
>run(111111111)
>
>print '>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>'
>print "2st test with run() to:10^10"
>run()
>
>print '>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>'
>print "3st test with fastrun() to:10^10 , Fastest!!!"
>fastrun()
>
>
>
>C++版
>/*
>一道据说是Google的面试题
>题目:有一个整数n,写一个函数f(n),返回0到n之间出现的"1"的个数。比如f(13)=6
>; f(11)=4,算出f(n)=n的n(如f(1)=1)？
>*/
>#include <cmath>
>#include <iostream>
>
>
>using namespace std;
>unsigned long long mypow(int a,int b)
>{
>unsigned long long sum=1;
>for(int i=0;i<b;i++)
>sum*=a;
>return sum;
>}
>unsigned long long count(unsigned long long 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)
>*/
>if(i==0)return 0;
>if(9>=i and i>=1)return 1;
>int digit=1;
>unsigned long long firstDigit=i;
>while(firstDigit>=10){
>firstDigit/=10;
>++digit;
>}
>
>unsigned long long now;
>unsigned long long rest=static_cast<unsigned long long
>int>(i-(firstDigit*mypow(10,digit-1)));
>if(firstDigit>1)now=static_cast<unsigned long long int>(mypow(10,digit-1));
>else{now=rest+1;}
>now+=static_cast<unsigned long long int>((digit-1)*mypow(10,digit-2) *
>firstDigit);
>
>
>return (now+count(rest));
>}
>
>unsigned long long little(unsigned long long i)
>{
>unsigned long long count_i=count(i);
>
>if(i<count_i){
>
>//i reduce 1 , count_i at most reduce 9 , so you at least reduce
>(count_i-i)/(9-1) to reach i==count_i
>if ((count_i-i)/8>1)return i-(count_i-i)/8;
>}
>
>if(i>count_i){
>//i reduce 1 , count_i at least reduce 0 , so you at least reduce
>(i-count_i) to reach i==count_i
>return count_i;
>}
>return i-1;
>}
>
>void run(unsigned long long i=pow(10.0f,10)){
>while (i>0){
>// print i,'=>i-count_i= ',i-count(i)
>if(i==count(i))cout<<i<<"=>"<<count(i)<<'\n';
>
>i=little(i);
>}
>cout<<"run() finished\n\n";
>}
>
>void fastrun(unsigned long long t=pow(10.0f,10)){
>//This just list out all this king of element :) But it is fastest and
>most useful
>const unsigned long long all[]={1, 199981, 199982, 199983, 199984,
>199985, 199986, 199987, 199988, 199989, 199990, 200000, 200001, 1599981,
>1599982, 1599983, 1599984, 1599985, 1599986, 1599987, 1599988, 1599989,
>1599990, 2600000, 2600001, 13199998, 35000000, 35000001, 35199981,
>35199982, 35199983, 35199984, 35199985, 35199986, 35199987, 35199988,
>35199989, 35199990, 35200000, 35200001, 117463825, 500000000, 500000001,
>500199981, 500199982, 500199983, 500199984, 500199985, 500199986,
>500199987, 500199988, 500199989, 500199990, 500200000, 500200001,
>501599981, 501599982, 501599983, 501599984, 501599985, 501599986,
>501599987, 501599988, 501599989, 501599990, 502600000, 502600001,
>513199998, 535000000, 535000001, 535199981, 535199982, 535199983,
>535199984, 535199985, 535199986, 535199987, 535199988, 535199989,
>535199990, 535200000, 535200001, 1111111110};
>for(int i=0;i!=83;++i){
>if(t>=all[i])cout<<all[i]<<'\n';
>}
>cout<<"fastrun() finished\n\n";
>}
>int main(int argc, char *argv[])
>{
>for(;;)
>{
>unsigned long long i;
>cout<<"please input a number:";
>cin>>i;
>cout<<"run():\n";
>run(i);
>cout<<"fastrun():\n";
>fastrun(i);
>}
>system("PAUSE");
>return EXIT_SUCCESS;
>
>}
>
>_______________________________________________
>Cpp mailing list
>Cpp at codingnow.com
>http://codingnow.com/mailman/listinfo/cpp
>
= = = = = = = = = = = = = = = = = = = =
致
礼！
李创
converse_lc at 163.com
2006-09-19
More information about the Cpp
mailing list