2007-03-14

求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).
  • CountOne.rar (889 Bytes)
  • 描述: 本文中的代码，贴上的代码有走样。
  • 下载次数: 26
评论
crackerwang 2007-08-17
想起PKU 3286和2282
当时要是看了你这篇肯定能瞬间AC
Godlikeme 2007-03-15
暂且叫查表吧，呵呵。
粗略想到一种不需要查表的logN 复杂度算法，还没有验证，待抽时间写出来。
simohayha 2007-03-14
很老的帖子了,看这个
http://www.javaeye.com/post/98905
Eastsun 2007-03-14
不叫速查表吧，只是把那些会多次用到的数据保存下来，避免重复递归（与动态规划有点像）。
Godlikeme 2007-03-14
抽时间看一下，使用了 速查表，速查表的生成没看太明白。
Eastsun
搜索本博客
我的相册
1b680e5a-efae-3ec3-8ccd-970a4a72a056-thumb
6.5beta.PNG
共 61 张
最近加入圈子
存档
最新评论