CSDN技术中心 GOOGLE面试题--我的答案

来源：百度文库 编辑：神马文学网 时间：2024/04/28 02:52:43
这个题目的英文原题是:
Consider a function which, for a given whole number n, returns the number of ones required when writing out all numbers between 0 and n.
For example, f(13)=6. Notice that f(1)=1. What is the next largest n such that f(n)=n?
翻译过来大体是这样：
有一个整数n,写一个函数f(n),返回0到n之间出现的"1"的个数。比如f(13)=6,现在f(1)=1,问下一个最大的f(n)=n的n是什么？
为什么f(13)=6, 因为1,2,3,4,5,6,7,8,9,10,11,12,13.数数1的个数，正好是6.
请大家写出自己的算法，并统计一些在你机器上计算出1111111110的时间。为了不影响大家的思路，我最后贴上我的程序。
语言不限，随便了。
CSDN论坛帖子链接：
google的一道面世题，算法高手进来看看
---------------------------------------------
我在原题的基础上“增加了难度”，即求出小于MAX的所有f(n)=n的数。
程序运行结果：
dex_c:2485 dex_f:4960 time:30
递归调用2485次，计算某个数的1的个数4960次（包括84次打印时的验证dummy调用），耗时30ms
说明：
foo--某个数的1的个数，我本来写了一个，原理一样，但代码没有这么漂亮，比较长，所以干脆直接用帖子里的一个算法；
思路--从1到MAX步长逐渐增大的2分法。
---------------------------------------------
#include
 
 
 
 
 
 
#include
 
typedef unsigned long number_t;
 
int count=0;
 
 
 
 
 
 
int dex_c=0;
 
 
 
 
 
 
int dex_f=0;
 
 
 
 
 
 
number_t foo(number_t n)
 
 
 
 
 
 
{
 
 
 
 
 
 
dex_f++;
 
 
 
 
 
 
number_t num, k, r, d;
 
 
 
 
 
 
number_t x;
 
 
 
 
 
 
for(num = k = r = 0, d = 1; n; n /= 10) {
 
 
 
 
 
 
x = n % 10;
 
 
 
 
 
 
num += x * k + (x > 1 ? d : (x == 1 ? r + 1 : 0));
 
 
 
 
 
 
r += x * d;
 
 
 
 
 
 
k = k * 10 + d;
 
 
 
 
 
 
d *= 10;
 
 
 
 
 
 
}
 
 
 
 
 
 
return num;
 
 
 
 
 
 
}
 
inline void found(number_t x)
 
 
 
 
 
 
{
 
 
 
 
 
 
printf("%d: f(%d)=%d\n",count+1,x,foo(x));count++;
 
 
 
 
 
 
}
 
void scan(number_t a,number_t b)
 
 
 
 
 
 
{
 
 
 
 
 
 
//     printf("scan %d %d\n",a,b);
 
 
 
 
 
 
if ((a>b)||(a<0)||(b<0)) return;
 
 
 
 
 
 
dex_c++;
 
 
 
 
 
 
number_t an=foo(a);
 
 
 
 
 
 
if (a==an) found(a);
 
 
 
 
 
 
if (a==b) return;
 
 
 
 
 
 
number_t bn=foo(b);
 
 
 
 
 
 
number_t k=a+(b-a)/2;
 
 
 
 
 
 
if ((a>bn) || (b 
 
 
 
 
 
if (k>=(a+1)) scan(a+1,k);
 
 
 
 
 
 
if ((k+2)<=b) scan(k+1,b-1);
 
 
 
 
 
 
if (b==bn) found(b);
 
 
 
 
 
 
 
 
 
 
 
 
}
 
int main ()
 
 
 
 
 
 
{
 
 
 
 
 
 
int t=GetTickCount();
 
 
 
 
 
 
const number_t MAX=3000000000L;
 
 
 
 
 
 
number_t n=1;
 
 
 
 
 
 
number_t i;
 
 
 
 
 
 
number_t k=1,p=1;
 
 
 
 
 
 
 
 
 
 
 
 
found(0);
 
 
 
 
 
 
while(1)
 
 
 
 
 
 
{
 
 
 
 
 
 
n=n*10;
 
 
 
 
 
 
 
 
 
 
 
 
for (i=1;i<=9;i++)
 
 
 
 
 
 
{
 
 
 
 
 
 
p=k;
 
 
 
 
 
 
k=i*n;
 
 
 
 
 
 
if (k>=MAX)
 
 
 
 
 
 
{
 
 
 
 
 
 
scan(p,MAX);
 
 
 
 
 
 
t=GetTickCount()-t;
 
 
 
 
 
 
printf("dex_c:%d dex_f:%d time:%d\n", dex_c, dex_f, t);
 
 
 
 
 
 
getchar();
 
 
 
 
 
 
return 0;
 
 
 
 
 
 
}
 
 
 
 
 
 
scan(p,k-1);
 
 
 
 
 
 
}
 
 
 
 
 
 
}
 
 
 
 
 
 
}
CSDN技术中心 GOOGLE面试题--我的答案 非技术面试题集 - CHRYSLER_300C的专栏 - CSDN博客 Google 的疯狂面试题 Google 的疯狂面试题 Google 的疯狂面试题 google搜索原理论文 - web开发 - CSDN技术中心 Linux行业招聘技术面试题汇总(含答案) - 大漠英豪的日志 - 网易博客 若干公务员面试题精选的答案 微软的面试题及答案 C语言面试题大汇总之微软亚洲技术中心面试题 Google 的疯狂面试题，你能答出几道？| CSDN技术中心 Log4j Google 面试题 Google 面试题 千万别入错行 导师送给我的15条人生建议 - 其他 - CSDN技术中心 千万别入错行 导师送给我的15条人生建议 - 其他 - CSDN技术中心 csdn - 调查：你遇到过怎样的java面试题 J2EE 面试题集锦 - sosboy923的专栏 - CSDN博客 哈佛面试题及答案 面试题（题型+答案） C#面试题与答案 哈佛面试题及答案 -- 微软面试题及答案 C#面试题和答案