趣談“面試算法”：一行代碼能幹啥？

2的幂

題目來源于 LeetCode 上第 231 号問題：2 的幂。題目難度為 Easy。

題目： 給定一個整數，編寫一個函數來判斷它是否是 2 的幂次方。

題目解析：

這個簡直可以說是“ 二進制 ”與“ 位運算 ”中的經典問題！

如果一個數是 2 的次方數的話，那麼它的二進數必然是最高位為1，其它都為 0 ，那麼如果此時我們減 1 的話，則最高位會降一位，其餘為 0 的位現在都為變為 1，那麼我們把兩數相與，就會得到 0。

代碼展示：

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return (n > 0) && (!(n & (n - 1)));
    } 
};      

3的幂

題目來源于 LeetCode 上第 326 号問題：3 的幂。題目難度為 Easy。

題目描述： 給定一個整數，寫一個函數來判斷它是否是 3 的幂次方。

題目解析：

正常的思路是不停地去除以 3，看最後的疊代商是否為 1。這種思路的代碼使用到了循環，逼格不夠高。

這裡取巧的方法 用到了 數論 的知識：3 的幂次的質因子隻有 3 。

題目要求輸入的是 int 類型，正數範圍是 0 - 231，在此範圍中允許的最大的 3 的次方數為 3^19 = 1162261467 ，那麼隻要看這個數能否被 n 整除即可。

代碼展示

class Solution {
    public boolean isPowerOfThree(int n) {
         return n > 0 && 1162261467 % n == 0;
    }
}      

那麼，這一題為什麼不用位運算和與運算？

這裡有個觀念需要注意一下： “取餘(%)操作中如果除數是 2 的幂次則等價于與其除數減一的與(&)操作（也就是說hash%length==hash&(length-1)的前提是 length 是 2 的 n 次方；）。” 并且 采用二進制位操作 &，相對于%能夠提高運算效率，這也就解釋了 HashMap 的長度為什麼是 2 的幂次方。

0的個數

題目來源于 LeetCode 上第 172 号問題：階乘後的零。題目難度為 Easy 。

題目： 給定一個整數 n，傳回 n! 結果尾數中零的數量。

public class Solution {
    public int trailingZeroes(int n) {
    //不斷遞歸
        return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);
    }
}