黑马程序员技术交流社区

标题: 计算1-400亿有多少个1?用JAVA做 [打印本页]
作者: 丶小天    时间: 2014-2-24 15:46
标题: 计算1-400亿有多少个1?用JAVA做
例如:
1到10有有 2 个1,
1到11有 4 个1;
好象方法没用对的话,跑出来特别费时间。。。。
好象别人2秒左右能跑出。方法用错的话能跑出但是要时间。N小时。。c++要快些。
最高记录1.6秒..
作者: joure    时间: 2014-2-24 16:47
本帖最后由 joure 于 2014-2-24 22:44 编辑


在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）
作者: l939    时间: 2014-2-24 16:56
围观结果，我就是来长见识的~~~
作者: 赵永生    时间: 2014-2-24 20:36
网上查的，据说是一道微软面试题：可以看一下。

  2. public class CountOne {

  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. }

  20. public static void main(String[] args){
  21.   System.out.println(CountOne.count1(new Long("101")));
  22. }
  23. }
复制代码
作者: qqwwdr    时间: 2014-2-24 22:32
自己写的，数到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. }
复制代码
作者: hdsjsql    时间: 2014-2-25 14:26
本帖最后由 hdsjsql 于 2014-2-25 22:12 编辑

写代码不容易，求技术分

  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.         }

  75. }
复制代码


22.PNG (1.39 KB, 下载次数: 20)

22.PNG
作者: 黑马_张伟    时间: 2014-2-25 19:41
hdsjsql 发表于 2014-2-25 14:26
写代码不容易，求技术分

可以问下，你们这种代码的块在论坛上怎么发？
作者: hdsjsql    时间: 2014-2-25 22:07
本帖最后由 hdsjsql 于 2014-2-25 22:18 编辑
黑马_张伟 发表于 2014-2-25 19:41
可以问下，你们这种代码的块在论坛上怎么发？

点击<>框，粘贴代码

code.png (3.77 KB, 下载次数: 18)

code.png
作者: 李白衣    时间: 2014-2-25 23:46
有 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




欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2