面試100 25從1到n正數中1出現的次數

          25從1到n正數中1出現的次數

   一問題描述：

求1到n中，十進制數中，1出現的次數總和
  方法1
     對每一個數x，x先與10取余，然后判斷x/10之后，是否為0，不為0則繼續上述操作
     復雜度為o(n)

  方法2：
     此題不要以為是重復計數，必須要重復計數，，因為100001 ，這個數字，需要記兩次，一次首位為1，另一次不計首位，后幾位為1.
     這樣的話，就有重復計數的問題了，但是本題求的是含有1的個數，所以需要被重復計數。
    
    
     使用遞歸21345
      則需要對21345的每一個10進制位，進行遞歸計算。對萬位，千位，百位，十位，個位
     
       即首位不為0，則可以分別計算21345 1345 345 45 5 
      1-20000
      20001-21000
      21001-21300
      21301-21340
      21341-21345
     
      (1) 當首位最高位為1時，含有1的個數為 10000
       首位可以為0 ， 1 ，則后四位其中有1位為1的個數為 ，2* 10(3)*4 = 8000  合計18000
       
       
     (2) 下面計算1345
        首位為1，則為  346
        其余位為 （首位可以為0） 3 * 10(2) = 30  合計376   
    
     (3)下面計算345
         首位為1  10的2次方
         首位可以為(0 1 2) 等于3的情況，  3 * 2 *10  合計160
         剩下的循環即求300- 345
        
     (4)下面計算45    
         首位為1， 10的1次方
         首位不計，首位可以取(0 1 2 3) 4 * 1  合計 14
      （5）下面計算5
         判斷長度小于1，直接返回

 擴展3 ：

    求1到n中任意進制的數的個數，遞歸公式如下：
        
       總結對于任意的1到n，求所給定的字符c的個數  
       s = abcdefgh , m = len(abcdefgh)     
        (1)當首位等于*s = c時 ，Q(abcdefgh) = abcdefgh + 1 + (*s-'0')*(m-1)*10^(m-2) + Q(bcdefgh)
        (2)當首位為 *s > c 時 ，Q(abcdefgh) = 10^(m-1) + (*s - '0') * (m-1) *10^(m-2) + Q(bcdefgh)
        (3)當首位為*s < c時，   Q(abcdefgh) =  (*s - '0') * (m-1) *10^(m-2) + Q(bcdefgh)
         
 三 代碼如下：
     

#include <iostream>
#include <cmath>
 using namespace std ;
 int sums(char * s)
 {
     int sum = 0 ;
     while(*s)
     {
       sum = sum * 10 + *s -  '0' ;
       s++ ;
             
     }
     
     return sum ;
 }
 
 int pows(int l)
 {
    int mul = 1 ; 
     for(int i = 1 ; i <= l ; i++)
        mul *= 10 ;
    return mul ;    
 }
 
 int solution2(char * s , char* c) //c表示查找含有c字符的數字的個數 
 {
     if(!s)
       return 0 ;
       
     int m = strlen(s) ;
     if(m == 1)
     {
       if(*s >= *c)
        return 1 ;
       else
        return 0 ;
     }
     //當首位為1的時候 
     if(*s == *c)     
       return  pows(m-2) * (m - 1)*( *s - '0')  + 1 + sums(s+1) + solution2(s+1 , c) ;      
     else
      if(*s > *c )    
       return pows(m-1) + pows( m-2) * (m - 1) * (*s - '0') + solution2(s+1 , c) ; 
      else
       return pows( m-2) * (m - 1) * (*s - '0') + solution2(s+1 , c) ;
          
        
     
 }
 
 
 int solution1(int n , int c)
 {
   int i = 1;
   int sum = 0 ;
   for(;i <= n ;i++)
   {
      int x = i ;    
      while(x)
      {
        if(x % 10 == c)
          sum++ ;
          x /= 10 ;      
      }               
   }
   
     return sum ;  
 }
 
   
 int main()
 {
   char s[100] = "21345" ; 
   char c[2] = "1" ;
   cout<<solution2(s , c) <<endl  ;
   cout<<solution1(21345 , 1) <<endl  ;
   system("pause") ;
   return 0 ;    
 }

posted on 2011-05-20 09:28 kahn 閱讀(731) 評論(0)  編輯 收藏 引用