求1~N中1出现的次数的递归算法

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

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

java 代码

import
 java.math.BigInteger;
import
 java.util.*;
/**
*求1到N这些数中1出现的次数
*@author Eastsun
*/
public
 
class
 CountOne{
    
private
 
static
 HashMap result =
new
 HashMap();

    
//计算countOne(10^n-1)
    
private
 
static
 BigInteger computeX(String num){
        BigInteger r =result.get(num.length());
        
if
(r==
null
){
            r =countOne(num);
            result.put(num.length(),r);
        }
        
return
 r;
    }
    
//得到一个表示10^n的BigInteger
    
private
 
static
 BigInteger getInteger(
int
 n){
        StringBuilder sb =
new
 StringBuilder(n+
1
);
        sb.append('
1
');
        
for
(
int
 i=
0
;i0
');
        
return
 
new
 BigInteger(sb.toString());
    }


    
//生成一个代表10^n-1的字符串,即n个9
    
private
 
static
 String getString(
int
 n){
        StringBuilder sb =
new
 StringBuilder(n);
        
for
(
int
 i=
0
;i9
');
        
return
 sb.toString();
    }
    
/**
    *计算从1到num这些数中1出现的次数
    *@param num 一个表示整数的字符串
    */
    
public
 
static
 BigInteger countOne(String num){
        
if
(num.length()==
1
){
            
if
(num.equals(
"0"
)) 
return
 BigInteger.ZERO;
            
else
                
return
 BigInteger.ONE;
        }

        BigInteger high,lower,remainder;

        
if
(num.charAt(
0
)=='
0
') high =BigInteger.ZERO;
        
else
 
if
(num.charAt(
0
)=='
1
') high =
new
 BigInteger(num.substring(
1
)).add(BigInteger.ONE);
        
else
  high =getInteger(num.length()-
1
);

        lower =computeX(getString(num.length()-
1
)).multiply(
new
 BigInteger(num.substring(
0
,
1
)));
        remainder =countOne(num.substring(
1
));
        
return
 high.add(lower).add(remainder);
    }

    
public
 
static
 
void
 main(String[] args){
        
long
 currentTime =System.currentTimeMillis();
        BigInteger bi =
new
 BigInteger(
"453454583828382932382932342342342423"
);
        
for
(
int
 n=
0
;n<
10
;n++){
            System.out.println(bi +
" :"
+countOne(bi.toString()));
            bi =bi.add(BigInteger.ONE);
        }
        
long
 det =System.currentTimeMillis() -currentTime;
        System.out.println(det);
    }
}

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

评论

5 楼 crackerwang 2007-08-17  

想起PKU  3286和2282
当时要是看了你这篇肯定能瞬间AC

4 楼 Godlikeme 2007-03-15  

暂且叫查表吧，呵呵。
粗略想到一种不需要查表的logN 复杂度算法，还没有验证，待抽时间写出来。

3 楼 simohayha 2007-03-14  

很老的帖子了,看这个
http://www.iteye.com/post/98905

2 楼 Eastsun 2007-03-14  

不叫速查表吧，只是把那些会多次用到的数据保存下来，避免重复递归（与动态规划有点像）。

1 楼 Godlikeme 2007-03-14  

抽时间看一下，使用了 速查表，速查表的生成没看太明白。