|
锁定老帖子 主题：google的一道面试题。
精华帖 (0) :: 良好帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2007-03-29
我把我的算法也贴出来
package untitled3;
import java.util.Date;
public class Untitled1 {
public Untitled1() {
}
public static void main(String[] args) {
Untitled1 untitled1 = new Untitled1();
//System.out.println(countOneNumberUnderN(199981));
findN();
}
public static void findN(){
long start = System.currentTimeMillis();
int count = 0;
for ( int i = 1; i < Integer.MAX_VALUE; i++ ){
count += countOneNumber(i);
if ( count == i ){
System.out.println("find "+i+","+(System.currentTimeMillis()-start)+"ms used!");
}
}
}
public static int countOneNumber(int n){
int count = 0;
while ( n > 0 ){
//模除10
int mod = n%10;
if ( mod == 1 )
count++;
n = n/10;
}
return count;
}
}
下面是运行结果 find 1,0ms used! find 199981,32ms used! find 199982,32ms used! find 199983,32ms used! find 199984,32ms used! find 199985,32ms used! find 199986,32ms used! find 199987,32ms used! find 199988,32ms used! find 199989,32ms used! find 199990,32ms used! find 200000,32ms used! find 200001,32ms used! find 1599981,329ms used! find 1599982,329ms used! find 1599983,329ms used! find 1599984,329ms used! find 1599985,329ms used! find 1599986,329ms used! find 1599987,329ms used! find 1599988,329ms used! find 1599989,329ms used! find 1599990,329ms used! find 2600000,532ms used! find 2600001,532ms used! find 13199998,3047ms used! find 35000000,8829ms used! find 35000001,8829ms used! find 35199981,8875ms used! find 35199982,8875ms used! find 35199983,8875ms used! find 35199984,8875ms used! find 35199985,8875ms used! find 35199986,8875ms used! find 35199987,8875ms used! find 35199988,8875ms used! find 35199989,8875ms used! find 35199990,8875ms used! find 35200000,8875ms used! find 35200001,8875ms used! find 117463825,32282ms used! |
| 返回顶楼 | |
|
发表时间：2007-04-08
都没有我的快：
http://www.jiehoo.com/google%e9%9d%a2%e8%af%95%e9%a2%98%e8%a7%a3%e8%af%b4%e6%80%a7%e8%83%bd%e4%b9%8b%e4%ba%94%ef%bc%9a%e4%ba%ba%e6%af%94%e7%94%b5%e8%84%91%e8%81%aa%e6%98%8e.htm Find 535199989, 7031ms Find 535199990, 7031ms Find 535200000, 7031ms Find 535200001, 7031ms Find 1111111110, 14250ms |
| 返回顶楼 | |
|
发表时间：2007-04-13
哈哈，首先我是来分析题目的。
我看到楼上的众多讨论其实都没有从根本上降低速度。 首先，在寻找“1”的个数上就没有数学方法吗？ 其次，在遍历1至MAX里就没有一下就提高位数的思想了吗？ 先引出讨论，再给出我的思路！！！ |
| 返回顶楼 | |
|
发表时间：2007-04-14
有。。。
用分治法+贪心算法 命中一个区域 之后用双循环会快。。。 Ｏ(log2n） |
| 返回顶楼 | |
|
发表时间：2007-04-16
呵呵。。
希望有人继续讨论讨论 用我的思路全算完才60ms 是全算完哦。。。 大家留意 楼上的可以写出具体过程，光说看不出效果。。。 |
| 返回顶楼 | |
|
发表时间：2007-04-16
有兴趣研究算法的可加群250581
请注明研究算法。。 |
| 返回顶楼 | |
|
发表时间：2007-04-16
你的全算完是什么意思？能够全算完吗？
|
| 返回顶楼 | |
|
发表时间：2007-04-16
的确。。。
有兴趣研究一下吗？ 加群。。。 只用60ms |
| 返回顶楼 | |
|
发表时间：2007-04-16
这样吧。。。我写一个让人深思的讨论。。。
如果是2进制下。。同让的题目。。答案是多少。。。 |
| 返回顶楼 | |
|
发表时间：2007-04-16
我的思路分两步：
1。查找f(n)=? 2。找出f(n)=n是多少？ 看起来好像很费力但是我的思想是前面都没见过的。。 我敢说我可以证明是最快的。。（除了语言上的优化外） |
| 返回顶楼 | |
