例如:
1到10有有 2 个1,
1到11有 4 个1;
好象方法没用对的话,跑出来特别费时间。。。。
好象别人2秒左右能跑出。方法用错的话能跑出但是要时间。N小时。。c++要快些。
最高记录1.6秒..

在eclipse大概测了一下使用for循环：for(long x=0; x<10000000000L;x++ ){ }
我的机子(i5的cpu)什么操作也不做跑了11857Millis，x++到10亿运行了11秒，400亿如果加上操作就算再优化没个几十分钟也跑不下来

如果使用循环遍历就跳进了出题者挖的一个大坑，我觉得这道题考的主要是分析问题的能力，编程实现倒是次要的

这个应该算是一道奥数题，勉强能跟编程扯上关系
逻辑思维，找规律

（0－9）共10个数字，每个数字出现一次10/10*1
（0－99）将1位数字前面给补0，那么就有200个数字,有数字1出现次数为100/10*1+100/100*10=20次
（0－999）我们将1位前面补2个0，将2位数字前面补一个0，那么有3000个数字，每个数字出现300次，1000/10*1+1000/100*10+1000/1000*100 =100*3=300
以此类推，
（0－9999）每个数字出现4000次 10^3*4
（0－99999）每个数字出现50000次 10^4*5
（0－999999）每个数字600000次
..........
算出规律： N位数中1最多出现的次数 = N*10^(N-1)-1
        最少为

十进制数在位数为10(十亿)~11(百亿)时到达临界点，1出现的次数首次超过该数字

（0－9999999999）每个数字出现10^11次
100 0000 0000 (10^11)以内1的出现次数为10^(11)+1 次


（0－40000000000）数字1出现1000000000×10×4+10000000000＝50000000000次
（01234）

围观结果，我就是来长见识的~~~

网上查的，据说是一道微软面试题：可以看一下。

1. 
   
2. public class CountOne {
   
3. 
   
4. private static long count1(Long n) {
   
5.      long count = 0;
   
6.      String num = n+"";
   
7.      Long x = (long)Math.pow(10, num.length()-1);
   
8.      for(int i=0; i<num.length(); i++) {
   
9.          count += Long.parseLong("0"+num.substring(0, i))*x;
   
10.          if(num.charAt(i)>'1') {
    
11.              count += x;
    
12.          }else if(num.charAt(i)=='1') {
    
13.              count += Long.parseLong("0"+num.substring(i+1))+1;
    
14.          }
    
15.          x /= 10;
    
16.      }
    
17.      return count;
    
18. }
    
19. 
    
20. public static void main(String[] args){
    
21.   System.out.println(CountOne.count1(new Long("101")));
    
22. }
    
23. }

复制代码

自己写的，数到1亿用了8秒多

1. public class TestOne
   
2. {
   
3.         public static void main(String[] args){
   
4.                 long l = System.currentTimeMillis();
   
5.                 int count = 0;
   
6.                 String str = null;
   
7.                 int i =-1;
   
8.                 int j=-1;
   
9.                 // 2的31次方－1=   2 147 483 648
   
10.                 for(i=1; i<100000000; i++)
    
11.                 {
    
12.                         str = String.valueOf(i);
    
13.                         for(j =0; j<str.length(); j++){
    
14.                                 if(str.charAt(j) == '1'){
    
15.                                         count++;
    
16.                                 }
    
17.                         }
    
18.                 }
    
19.                 System.out.println( "时间：" + (System.currentTimeMillis()-l)  + " :1的个数 " + count);
    
20.         }
    
21. }

复制代码

写代码不容易，求技术分

1. 
   
2. public class Count {
   
3.         public static void main(String[] args) {
   
4.                 long before = System.currentTimeMillis();
   
5.                 long count = getSum();
   
6.                 long after = System.currentTimeMillis();
   
7.                 System.out.println("1到400亿中1的个数为："+count);        
   
8.         //        System.out.println(count+"==");
   
9.                 System.out.println("time:"+(after-before));
   
10.                
    
11.         }
    
12.         
    
13.         public static long getSum(){
    
14.                 long sum = 0;
    
15.                 long c;
    
16.                 for(int i=1;i<=11;i++){        
    
17.                          c = test(i);
    
18.                          System.out.println("当400亿中出现"+i+"个位置是1时");        
    
19.                          System.out.println("1的个数为："+c);
    
20.                          System.out.println();
    
21.                         sum+=c;
    
22.                 }
    
23.                
    
24.                 return sum;
    
25.         }
    
26.         
    
27.         public static long test(int x){
    
28.                 int t,w;
    
29.                 long y=1,z=1,c=1,d=1;
    
30.                 long s1=1,s2=1;
    
31.                 long sum1,sum2;
    
32.                
    
33.                 System.out.println("当400亿中出现"+x+"个位置是1时");               
    
34.                 System.out.println("最高位不为1");
    
35.                
    
36.         
    
37.                 for(int i=1,j=0;i<=x;i++,j++){
    
38.                   y*=10-j;
    
39.                 }               
    
40.                 t=x;
    
41.                 while(t>0){
    
42.                         c*=t;
    
43.                         t--;
    
44.                 }
    
45.                
    
46.                 s1=y/c;
    
47.                 System.out.println("s1:"+s1);
    
48.                 sum1=s1*3;//最高位只能取0,2,3
    
49.                 for(int i=0;i<10-x;i++){
    
50.                         sum1 *=9;                                                
    
51.                 }
    
52.                 System.out.println("1的个数为:"+sum1);
    
53.                
    
54.                
    
55.                 System.out.println("最高位为1");
    
56.                 for(int i=1,j=0;i<=x-1;i++,j++){
    
57.                           z*=10-j;
    
58.                         }        
    
59.                 w=x-1;
    
60.                 while(w>0){
    
61.                         d*=w;
    
62.                         w--;
    
63.                 }
    
64.                 s2=z/d;
    
65.                 System.out.println("s2:"+s2);
    
66.                 sum2=s2;
    
67.                 for(int i=0;i<10-x+1;i++){
    
68.                         sum2 *=9;                                                
    
69.                 }
    
70.                 System.out.println("1的个数为:"+sum2);
    
71.                
    
72.                 return (sum1+sum2)*x;
    
73.         }
    
74. 
    
75. }
    

复制代码

hdsjsql 发表于 2014-2-25 14:26
写代码不容易，求技术分

可以问下，你们这种代码的块在论坛上怎么发？

黑马_张伟 发表于 2014-2-25 19:41
可以问下，你们这种代码的块在论坛上怎么发？

点击<>框，粘贴代码

有 11 位数，
当第一位为 1 的时候，其余每位都有10种可能，有 1 * 10^10 个 1
当第二位为 1 的时候，第一位有4种可能，其余每位都有10种可能，有 4*1*10^9 个 1
。。。
当最后一位为1的时候，有 4*10^9*1 个 1
一共：10^10 + 4*10^10 = 5*10^10