|
锁定老帖子 主题：google的一道面试题。
精华帖 (0) :: 良好帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2007-04-16
还有我是全算完才60ms
不是只算一个用了60ms 楼主要说算到1111111110用了0ms有过其实吧。 |
| 返回顶楼 | |
|
发表时间：2007-04-17
mjy304122 写道 还有我是全算完才60ms
不是只算一个用了60ms 楼主要说算到1111111110用了0ms有过其实吧。 那个 C 程序就摆在那里，你好歹弄下来编译运行尝试一下再说好吧？ |
| 返回顶楼 | |
|
发表时间：2007-04-17
我就不再卖关子了。。。。。。。
既然，很多人都还停留在追求所谓速度上。。。。 对于2进制 f(1)=1,f(10)=10 就再没有符合了 3进制 f(1)=1,f(11)=11,f(12)=12,f(110)=110 4进制 符合的有 1，121，122，123，130，200，201，1110 。。。。。。。 。。。。。。。 十进制最后的就是f(1111111110)=1111111110 还有以下是求f(n)的方法count(n)是直接算的。。。 对任何进制可用，2进制的话q=q*2，当然除也是除十。。。 绝对比以上的求f(n)的方法快，当然还可以再加工一下 还有最主要的如何提高遍历的速度，就是楼主说的剪枝（我人为我的方法也不能称为剪枝） 我用了很简单的思想以后再说。。。。。 当然，为什么1111111110是最大，这是函数变化率的问题，大家朝这个方向想想就明白了。 time=0; q=1; public int count(int n){ clear(); num=n; tem1=n; temp(n); while(tem1!=0){ q=q*10; temp(tem1); } //System.out.print(time); //System.out.println(); //System.out.println(); return time; } private void temp(int n){ int a=n/10; int b=n%10; tem1=a; time=time+a*q; if(b>1) time=time+q; else if(b==1) time=time+num%q+b; } |
| 返回顶楼 | |
|
发表时间：2007-04-22
mjy304122 写道 我还没有说我的思路。。。。
我只是说上面众多讨论中我觉得f(9),f(99).. 这种思路还算快，但是我还是觉得他慢。。。 剪枝，我觉得还要看怎剪，不相信我先给结果。。。 程序以后再给。。。 结果。。后面还有1111111110 和10000000000由于溢出所以没算。。 1,0ms used! 199981,0ms used! 199982,0ms used! 199983,0ms used! 199984,0ms used! 199985,0ms used! 199986,0ms used! 199987,0ms used! 199988,0ms used! 199989,0ms used! 199990,0ms used! 200000,0ms used! 200001,0ms used! 1599981,16ms used! 1599982,16ms used! 1599983,16ms used! 1599984,16ms used! 1599985,16ms used! 1599986,16ms used! 1599987,16ms used! 1599988,16ms used! 1599989,16ms used! 1599990,16ms used! 2600000,16ms used! 2600001,16ms used! 35000000,16ms used! 35000001,16ms used! 35199981,31ms used! 35199982,47ms used! 35199983,47ms used! 35199984,47ms used! 35199985,47ms used! 35199986,47ms used! 35199987,47ms used! 35199988,47ms used! 35199989,47ms used! 35199990,47ms used! 35200000,47ms used! 35200001,47ms used! 500000000,47ms used! 500000001,47ms used! 500199981,47ms used! 500199982,47ms used! 500199983,47ms used! 500199984,47ms used! 500199985,47ms used! 500199986,47ms used! 500199987,47ms used! 500199988,62ms used! 500199989,62ms used! 500199990,62ms used! 500200000,62ms used! 500200001,62ms used! 501599981,62ms used! 501599982,62ms used! 501599983,62ms used! 501599984,62ms used! 501599985,62ms used! 501599986,62ms used! 501599987,62ms used! 501599988,62ms used! 501599989,62ms used! 501599990,62ms used! 502600000,62ms used! 502600001,62ms used! 535000000,62ms used! 535000001,62ms used! 535199981,62ms used! 535199982,62ms used! 535199983,62ms used! 535199984,62ms used! 535199985,62ms used! 535199986,62ms used! 535199987,62ms used! 535199988,62ms used! 535199989,62ms used! 535199990,62ms used! 535200000,62ms used! 535200001,62ms used! 怎么没有f(13199998) = 13199998 ？ 复制粘贴的时候弄错了？还是算法问题？ 我机器上没有c，用java做了个，结果如下： 1,0ms 199981,0ms 199982,0ms 199983,0ms 199984,0ms 199985,0ms 199986,0ms 199987,0ms 199988,0ms 199989,0ms 199990,0ms 200000,0ms 200001,0ms 1599981,15ms 1599982,15ms 1599983,15ms 1599984,15ms 1599985,15ms 1599986,15ms 1599987,15ms 1599988,15ms 1599989,15ms 1599990,15ms 2600000,15ms 2600001,15ms 13199998,15ms 35000000,15ms 35000001,15ms 35199981,31ms 35199982,31ms 35199983,31ms 35199984,31ms 35199985,31ms 35199986,31ms 35199987,31ms 35199988,31ms 35199989,31ms 35199990,31ms 35200000,31ms 35200001,31ms 117463825,31ms 500000000,31ms 500000001,31ms 500199981,31ms 500199982,31ms 500199983,31ms 500199984,31ms 500199985,31ms 500199986,31ms 500199987,31ms 500199988,31ms 500199989,31ms 500199990,31ms 500200000,31ms 500200001,31ms 501599981,47ms 501599982,47ms 501599983,47ms 501599984,47ms 501599985,47ms 501599986,47ms 501599987,47ms 501599988,47ms 501599989,47ms 501599990,62ms 502600000,62ms 502600001,62ms 513199998,62ms 535000000,78ms 535000001,78ms 535199981,78ms 535199982,78ms 535199983,78ms 535199984,78ms 535199985,78ms 535199986,78ms 535199987,78ms 535199988,78ms 535199989,78ms 535199990,78ms 535200000,78ms 535200001,78ms 1111111110,78ms |
| 返回顶楼 | |
