论坛首页 → 入门技术论坛 →

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

浏览 5520 次
锁定老帖子 主题：求1~N中1出现的次数的递归算法
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
作者 正文
  • Eastsun
  • 等级: 二钻会员
  • 性别:
  • 文章: 790
  • 积分: 1329
  • 来自: 天津
   发表时间：2007-03-14  

        在网上看到的一个算法题，据说是某个大公司的面试题。题目如下:给出一个数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
返回顶楼
         
  • Godlikeme
  • 等级: 一钻会员
  • 性别:
  • 文章: 1159
  • 积分: 744
  • 来自: 北京
   发表时间：2007-03-14  
抽时间看一下，使用了 速查表，速查表的生成没看太明白。
返回顶楼
          回帖地址
0 请登录后投票
  • Eastsun
  • 等级: 二钻会员
  • 性别:
  • 文章: 790
  • 积分: 1329
  • 来自: 天津
   发表时间：2007-03-14  
不叫速查表吧，只是把那些会多次用到的数据保存下来，避免重复递归（与动态规划有点像）。
返回顶楼
          回帖地址
0 请登录后投票
  • simohayha
  • 等级: 一钻会员
  • 性别:
  • 文章: 1513
  • 积分: 951
  • 来自: 火星
   发表时间：2007-03-14  
很老的帖子了,看这个
http://www.iteye.com/post/98905
返回顶楼
          回帖地址
0 请登录后投票
  • Godlikeme
  • 等级: 一钻会员
  • 性别:
  • 文章: 1159
  • 积分: 744
  • 来自: 北京
   发表时间：2007-03-15  
暂且叫查表吧，呵呵。
粗略想到一种不需要查表的logN 复杂度算法，还没有验证，待抽时间写出来。
返回顶楼
          回帖地址
0 请登录后投票
  • crackerwang
  • 等级: 初级会员
  • 性别:
  • 文章: 10
  • 积分: 30
  • 来自: 北京
   发表时间：2007-08-17  
想起PKU  3286和2282
当时要是看了你这篇肯定能瞬间AC
返回顶楼
          回帖地址
0 请登录后投票
论坛首页 → 入门技术版

跳转论坛:
Global site tag (gtag.js) - Google Analytics