一道微软面试题,计算1-400亿有多少个1?用JAVA做.

来源：百度知道 编辑：UC知道 时间：2024/06/14 16:30:34
例如:
1到10有有 2 个1,1到11有 3 个1;
好象方法没用对的话,跑出来要的是时间.
不好意思,1-11有4个1...上面说错了.
好象别人2秒左右能跑出。方法用错的话能跑出但是要时间。N小时。。c++要快些。
最高记录1.6秒..

//package com.color.program;

public class CountOne {

private static long count1(Long n) {
long count = 0;
String num = n+"";
Long x = (long)Math.pow(10, num.length()-1);
for(int i=0; i<num.length(); i++) {
count += Long.parseLong("0"+num.substring(0, i))*x;
if(num.charAt(i)>'1') {
count += x;
}else if(num.charAt(i)=='1') {
count += Long.parseLong("0"+num.substring(i+1))+1;
}
x /= 10;
}
return count;
}

public static void main(String[] args){
System.out.println(CountOne.count1(new Long("101")));
}
}

这题的核心是用递归，我昨天晚上做了测试，最多可以读到4亿，超过了就内存溢出，我很想知道有没有真的能读到400亿的方法，期待。。。。

讲解