欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

求1~N中1出现的次数的递归算法 博客分类: 算法相关 算法面试 

程序员文章站 2024-02-16 20:56:22
...

        在网上看到的一个算法题,据说是某个大公司的面试题。题目如下:给出一个数n,求1到n这些数中1出现的次数

       这个题是典型的用递归算法来解决的,代码如下:

java 代码
  1. import  java.math.BigInteger;   
  2. import  java.util.*;   
  3. /**  
  4. *求1到N这些数中1出现的次数  
  5. *@author Eastsun  
  6. */   
  7. public   class  CountOne{   
  8.      private   static  HashMap result = new  HashMap();   
  9.        
  10.      //计算countOne(10^n-1)   
  11.      private   static  BigInteger computeX(String num){   
  12.         BigInteger r =result.get(num.length());   
  13.          if (r== null ){   
  14.             r =countOne(num);   
  15.             result.put(num.length(),r);   
  16.         }   
  17.          return  r;   
  18.     }   
  19.      //得到一个表示10^n的BigInteger   
  20.      private   static  BigInteger getInteger( int  n){   
  21.         StringBuilder sb = new  StringBuilder(n+ 1 );   
  22.         sb.append(' 1 ');   
  23.          for ( int  i= 0 ;i0 ');   
  24.          return   new  BigInteger(sb.toString());   
  25.     }   
  26.        
  27.   
  28.      //生成一个代表10^n-1的字符串,即n个9   
  29.      private   static  String getString( int  n){   
  30.         StringBuilder sb = new  StringBuilder(n);   
  31.          for ( int  i= 0 ;i9 ');   
  32.          return  sb.toString();   
  33.     }   
  34.      /**  
  35.     *计算从1到num这些数中1出现的次数  
  36.     *@param num 一个表示整数的字符串  
  37.     */   
  38.      public   static  BigInteger countOne(String num){   
  39.          if (num.length()== 1 ){   
  40.              if (num.equals( "0" ))  return  BigInteger.ZERO;   
  41.              else                  return  BigInteger.ONE;   
  42.         }   
  43.            
  44.         BigInteger high,lower,remainder;   
  45.            
  46.          if (num.charAt( 0 )==' 0 ') high =BigInteger.ZERO;   
  47.          else   if (num.charAt( 0 )==' 1 ') high = new  BigInteger(num.substring( 1 )).add(BigInteger.ONE);   
  48.          else   high =getInteger(num.length()- 1 );   
  49.            
  50.         lower =computeX(getString(num.length()- 1 )).multiply( new  BigInteger(num.substring( 0 , 1 )));   
  51.         remainder =countOne(num.substring( 1 ));   
  52.          return  high.add(lower).add(remainder);   
  53.     }   
  54.        
  55.      public   static   void  main(String[] args){   
  56.          long  currentTime =System.currentTimeMillis();   
  57.         BigInteger bi = new  BigInteger( "453454583828382932382932342342342423" );   
  58.          for ( int  n= 0 ;n< 10 ;n++){   
  59.             System.out.println(bi + " :" +countOne(bi.toString()));   
  60.             bi =bi.add(BigInteger.ONE);   
  61.         }   
  62.          long  det =System.currentTimeMillis() -currentTime;   
  63.         System.out.println(det);   
  64.     }   
  65. }  

          注意代码里面用到了一个HashMap来保存10^n-1那些数的对应值,这段代码比较重要,如果不要的话,算法的时间复杂度将达到 O(N^(1/3)) (精确的说:其中n的指数是ln2/ln10 ) ;而加上后,算法的时间复杂度降低到O(logN).

  • CountOne.rar (889 Bytes)
  • 描述: 本文中的代码,贴上的代码有走样。
  • 下载次数: 62
相关标签: 算法 面试