一道据说是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<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++代码
-------------------------------------------------------------------------------
#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;

}
posted on 2006-09-16 10:49 张沈鹏 阅读(1660) 评论(8)  编辑 收藏 引用
Comments
  • # re: 一道据说是Google的面试题(我用python写的快速算法,希望大家狠狠地批评)
    chenger
    Posted @ 2006-09-16 15:04
    学习。little函数比较巧妙。  回复  更多评论   
  • # re: 一道据说是Google的面试题
    fish
    Posted @ 2006-11-01 20:30
    Public Class Form1

    Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load


    End Sub

    Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
    If Me.TextBox1.Text <> "" Then
    change(Me.TextBox1.Text)
    Else
    MessageBox.Show("有错误")
    End If
    End Sub
    Public Function change(ByVal dan As String) As Integer
    Dim i, j, h As Integer
    Dim f, o As String
    Dim g As Integer
    Dim m As Integer = 0

    i = CType(dan, Integer)
    If i > 0 Then


    For j = 1 To i
    f = CStr(j)
    g = f.Length
    For h = 0 To g - 1
    o = f.Chars(h)
    If String.Compare(o, "1") = 0 Then
    m += 1

    Else
    End If
    Next
    Next

    Me.TextBox2.Text = CStr(m)
    Else
    MessageBox.Show("有错误")
    End If
    End Function


    End Class  回复  更多评论   
  • # re: 一道据说是Google的面试题
    一米
    Posted @ 2006-11-08 13:24
    该题的C++ 代码部分有误,至少在VC下编译通不过! 请作者修改修改……  回复  更多评论   
  • # re: 一道据说是Google的面试题
    张沈鹏
    Posted @ 2006-11-08 14:16
    我用g++试了一下没问题啊,
    vc2005应该也是没问题的,
    难道你用的是VC6?  回复  更多评论   
  • # re: 一道据说是Google的面试题
    tigerkin
    Posted @ 2006-12-25 18:05
    采用递归函数可以实现伪代码:呵呵没有测试过,不知道行不行

    long f(long n)
    {
    long num = 0; //累计0到n之间出现的"1"的个数
    long n1 = n;

    //如果n等于1,返回1;
    if (n == 1 )
    return 1;

    //从个位数到高位数的顺序开始检查,计算整数n1包含“1”的个数
    while(n1/10 != 0)
    {
    //如果整数n1的末位数是“1”,累计
    if (n1%10 == 1)
    num++;

    //去掉整数n1的最末位数,继续计算
    n1 = n1/10;
    }

    //处理n的最高位数是否为“1”
    if (n1 == 1)
    num ++;

    //做递归处理
    return num += f(n-1);

    }  回复  更多评论   
  • # re: 一道据说是Google的面试题
    zsp
    Posted @ 2006-12-25 19:06
    :)
    不需要一个一个验证
      回复  更多评论   
  • # re: 一道据说是Google的面试题
    tigerkin
    Posted @ 2006-12-26 09:01
    呵呵,已经好几年没有编程了,昨天在你的站点上看到Google的题目,心血来潮,写了以上思路。
    你的站点挺不错,我目前正在研究有关P2P在流媒体领域的应用,如果可以我们建个友情链接,互相学习。^_^

    我的站点名称:起跑者2.0 | Starting-runner
    地址:http://hi.baidu.com/tigerchen/
    主题:起跑者2.0 | Starting-runner >>> 积累是创新的开始!   回复  更多评论   
  • # re: 一道据说是Google的面试题
    张沈鹏
    Posted @ 2006-12-29 22:00
    可以阿,我现建了  回复  更多评论   

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理