LintCode算法题整理（一）

A + B 问题、尾部的零、统计数字

1.A + B 问题：给出两个整数a和b, 求他们的和, 但不能使用 + 等数学运算符。

int aplusb(int a, int b) {
    //采用异或运算^（不进位加法）
    //先进行异或，然后a&b获取进位，左移一位，直到没有进位
    while(b!=0){ 
        int c=a^b;//异或（不进位加法）
        int d=(a&b)<<1;//应进位的左移一位
        a=c;
        b=d;
    }
    return a;
}

2.尾部的零:设计一个算法，计算出n阶乘中尾部零的个数

样例:11! = 39916800，因此应该返回 2

思路一：先计算阶乘，再计算0的个数，，时间复杂度太高

class Solution {
public:    
/*     
* @param n: A long integer     
* @return: An integer, denote the number of trailing zeros in n!     
*/    
long long fac(long long n){
    if(n==0)
        return 1;
    if(n==1) 
        return 1;
    else
        return fac(n-1)*n; 
 }    
 long long trailingZeros(long long n) {
     // write your code here, try to do it without arithmetic operators. 
     //设计一个算法，计算出n阶乘中尾部零的个数 
     //先计算阶乘，然后取余10计算0的个数
     long long m=fac(n);
     long long t=0;
     while(m%10==0){ 
         t++; 
         m=m/10;
     }
     return t;
     }
};

思路二：若末尾产生0，则肯定包括5,10,15,20,25.。。。

1,2,3,4,---------0=1/5

5,6,7,8,9,--------1=5/5

10,11,12,13,14,----2=10/5

15,16,17,18,19,----3=15/5

20,21,22,23,24,----4=20/5

25,26,27,28,29,----6=25/5+5/5

class Solution {
public:
/* 
* @param n: A long integer
* @return: An integer, denote the number of trailing zeros in n!
*/ 
long long trailingZeros(long long n) {
    // write your code here, try to do it without arithmetic operators.
    long count=0;
    long temp=n/5;
    while(temp!=0){  
        count+=temp; 
        temp/=5;
    }
    return count;
}
};

3.统计数字：计算数字k在0到n中的出现的次数，k可能是0~9的一个值

样例：例如n=12，k=1，在 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]，我们发现1出现了5次 (1, 10, 11, 12)

思路，从k到n一次计算每个数包含k的个数，相加。

class Solution {
public:    
/*     
* @param : An integer     
* @param : An integer    
* @return: An integer denote the count of digit k in 1..n    
 */     
 //计算某个数i中含有k的个数     
 int calCount(int i,int k){
     int s=0;//个数统计 
     while(i/10!=0){
         //依次从右到左比对当前位是否等于k 
         if(i%10==k)
             s++; 
         //去掉末尾
         i=i/10;
     }
     //判断最高位是否为k 
     if(i==k) 
         s++;
     return s;
 }   
 int digitCounts(int k, int n) {
      // write your code here 
      //从k到n，依次计算包含k的个数
      int sum=0;
      for(int i=k;i<=n;i++){
          sum+=calCount(i,k);
      } 
      return sum; 
  }
};