首页 > 代码库 > LintCode 刷题记录

LintCode 刷题记录

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

思路:使用^来求当前位置上的值,用&来求每个位置上的进位,进位向前移动一位后继续循环,直到进位为0。

技术分享
class Solution {
public:
    /*
     * @param a: The first integer
     * @param b: The second integer
     * @return: The sum of a and b
     */
    int aplusb(int a, int b) {
        // write your code here, try to do it without arithmetic operators.
        int res = a ^ b, carry = (a & b) << 1;
        while (carry != 0) {
            int temp = res ^ carry;
            carry = (res & carry) << 1;
            res = temp;
        }
        return res;
    }
};
A + B 问题

记录: (1) 一刷 BUG FREE

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

思路:所有的尾部0都是来自于10因子,而10来自于因子2和5。2的数量是充分的,因此0的个数取决于1~n中包含5的因子的个数。每5个数出现一个因子5,每25个数多出现一个因子,每125个数再多出现一个因子。

技术分享
 1 class Solution {
 2 public:
 3     // param n : description of n
 4     // return: description of return 
 5     long long trailingZeros(long long n) {
 6         long long res = 0;
 7         while (n > 0) {
 8             res += n / 5;
 9             n = n / 5;
10         }
11         return res;
12     }
13 };
View Code

记录:(1) 一刷 BUG FREE

LintCode 刷题记录