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

        在网上看到的一个算法题，据说是某个大公司的面试题。题目如下:给出一个数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).