一行代碼解決了三個常考演算法題，面試官懵了

大家耐心看完，以后遇到相關問題，就可以裝個逼了，另外，帥地也正在整理一些面試相關的資料，文末把最近整理的長達 20 萬字的《Java面試必知必會》送給大家，

1、n 的階乘

問題描述：給定一個整數 N，那么 N 的階乘 N! 末尾有多少個 0？例如： N = 10，則 N！= 3628800，那么 N! 的末尾有兩個0，

我先給出個代碼讓大家品嘗一下，在細細講解

int f(n){
	return n == 0 ? 0 : n / 5 + f(n / 5);
}

對于這道題，常規操作是直接算 N！的值再來除以 10 判斷多少個 0 ，然而這樣肯定會出現溢位問題，并且時間復雜度還大，我們不妨從另一個思路下手：一個數乘以 10 就一定會在末尾產生一個零，那么，我們是否可以從哪些數相乘能夠得到 10 入手呢？

答是可以的，并且只有 2 * 5 才會產生 10，

注意，4 * 5 = 20 也能產生 0 啊，不過我們也可以把 20 進行分解啊，20 = 10 * 2，

于是，問題轉化為 N! 種能夠分解成多少對 2*5，再一步分析會發現，在 N！中能夠被 2 整除的數一定比能夠被 5 整除的數多，于是問題近似轉化為求 1…n 這 n 個數中能夠被 5 整除的數有多少個，

注意，像 25 能夠被 5整除兩次，所以25是能夠產生 2 對 2 * 5滴，有了這個思路，代碼如下：

int f(int n){
    int sum = 0;
    for(int i = 1; i <= n; i++){
        int j = i;
        while(j % 5 == 0){
            sum++;
            j = j / 5;
        }
    }
    return sum;
}

然而進一步拆解，我們發現

當 N = 20 時，1~20 可以產生幾個 5 ？答是 4 個，此時有 N / 5 = 4，

當 N = 24 時，1~24 可以產生幾個 5 ？答是 4 個，此時有 N / 5 = 4，

當 N = 25 時，1~25 可以產生幾個 5？答是 6 個，主要是因為 25 貢獻了兩個 5，此時有 N / 5 + N / 5^2 = 6，

…

可以發現 產生 5 的個數為 sum = N/5 + N/5^2 + N/5^3+….

于是，一行代碼就可以搞定它了

int f(n){
	return n == 0 ? 0 : n / 5 + f(n / 5);
}

別問，問就是一行代碼的事，

2、2 的冪次方

問題描述：判斷一個整數 n 是否為 2 的冪次方

對于這道題，常規操作是不斷這把這個數除以 2，然后判斷是否有余數，直到 n 被整除成 1 ，

我們可以把 n 拆成二進制看待處理的，如果 n 是 2 的冪次方的話，那么 n 的二進制數的最高位是 1，后面的都是 0，例如對于 16 這個數，它的二進制表示為 10000，

如果我們把它減 1，則會導致最高位變成 0，其余全部變成 1，例如 10000 - 1 = 01111，

然后我們把 n 和 （n - 1）進行與操作，結果就會是 0，例如(假設 n 是 16)

n & (n-1) = 10000 & （10000 - 1) = 10000 & 01111 = 0

也就是說，n 如果是 2 的冪次方，則 n & (n-1) 的結果是 0，否則就不是，所以代碼如下

int isPow(n){
	return (n & (n - 1)) == 0;
}

一行代碼搞定，在裝逼的路上越走越遠

3、找出一個沒有重復的數

給你一組整型資料，這些資料中，其中有一個數只出現了一次，其他的數都出現了兩次，讓你來找出一個數 ，

這道題可能很多人會用一個哈希表來存盤，每次存盤的時候，記錄 某個數出現的次數，最后再遍歷哈希表，看看哪個數只出現了一次，這種方法的時間復雜度為 O(n)，空間復雜度也為 O(n)了，

然而我想告訴你的是，采用位運算來做，絕對高逼格！

我們剛才說過，兩個相同的數異或的結果是 0，一個數和 0 異或的結果是它本身，所以我們把這一組整型全部異或一下，例如這組資料是：1， 2， 3， 4， 5， 1， 2， 3， 4，其中 5 只出現了一次，其他都出現了兩次，把他們全部異或一下，結果如下：

由于異或支持交換律和結合律，所以:

1²3⁴5¹2³4 = （1¹⁾(2²⁾(3³⁾(4⁴⁾5= 0⁰0⁰5 = 5，

也就是說，那些出現了兩次的數異或之后會變成0，那個出現一次的數，和 0 異或之后就等于它本身，就問這個解法牛不牛逼？所以代碼如下

int find(int[] arr){
    int tmp = arr[0];
    for(int i = 1;i < arr.length; i++){
        tmp = tmp ^ arr[i];
    }
    return tmp;
}

時間復雜度為 O(n)，空間復雜度為 O(1)，而且看起來很牛逼，就問這波操作穩不穩？

這里說明一下，這個方式適合一個數出現了奇數次，其他數都出現了偶數次

不行，我還要繼續裝！

？一行代碼解決方案如下：

// 例如使用這個函式的時候，我們最開始傳給 i 的值是 1，傳給 result 的是 arr[0]
//例如 find(arr, 1, arr[0])
int find(int[] arr,int i, int result){
	return arr.length <= i ? result : find(arr, i + 1, result ^ arr[i]);
}

實不相瞞，這道題用了一行代碼之后，更加復雜 + 難懂了，，，，，，不好意思，我錯了，不該把簡單的問題搞復雜了再扔給面試題的，

另外，校招就要來了，帥地為大家整理了一份面試題，這份面試題，算是 Java 一整套技術堆疊都寫了，包括 Java 基礎，虛擬機，訊息佇列，框架等等，

當然，還有通用基礎知識，例如計算機網路，作業系統，Mysql，Redis 也都整理了，給大家看一下目錄，

一方面也是方便自己以后跳槽的時候復習，相信這份面試題一定在面試和復習的程序中助大家一臂之力，送給大家，在帥地的公眾號「帥地玩編程」后臺回復「Java面試題」就可以獲取到了，

有時候經常收到讀者提問，例如

Java 應該要學習到哪個程度啊？

資料結構與演算法要學習到哪個程度啊？

計算機基礎要學習到哪個程度啊？

這其實很難衡量，我一般給的建議就是，把一本書 80% 的知識點啃完，我覺得就差不多了，

例如你說 mysql 要學到哪個程度，那么你只需把《mysql必知必會》和《MySQL技術內幕》看完，那么就差不多了，剩下的，以后遇到不懂的再去看文章即可，

不過呢，驗證自己學的如何，還有另外一種可行方式，就是看看市面上的面試題，你掌握了多少？，帥地整理的這份 PDF，應該就適合你了，只求來個贊，嘻嘻，

作者簡潔

作者：大家好，我是帥地，從大學、自學一路走來，深知演算法，計算機基礎知識的重要性，公眾號「帥地玩編程」10萬粉絲作者，專業于寫這些底層知識，提升我們的內功，帥地期待你的關注，和我一起學習，點擊了解我四年大學學 習之路 轉載說明：未獲得授權，禁止轉載