面试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 阅读(710) 评论(0)  编辑 收藏 引用