java算法題目及答案介紹

一、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;
}

二、約瑟夫環實現

問題描述：編號為 1-N 的 N 個士兵圍坐在一起形成一個圓圈，從編號為 1 的士兵開始依次報數（1，2，3…這樣依次報），數到 m 的 士兵會被殺死出列，之后的士兵再從 1 開始報數。直到最后剩下一士兵，求這個士兵的編號。

先給出代碼，后面在解釋。

int f(int n, int m){
    return n == 1 ? n : (f(n - 1, m) + m - 1) % n + 1;
}

原理是這樣的：

如果我們把士兵刪除后，重新給這些士兵編號的話，那么刪除前和刪除后，這些編號存在某種數學關系，我們只需要找出這個關系即可。

我們定義遞歸函數 f(n，m) 的返回結果是存活士兵的編號，顯然當 n = 1 時，f(n, m) = 1。假如我們能夠找出 f(n，m) 和 f(n-1，m) 之間的關系的話，我們就可以用遞歸的方式來解決了。我們假設人員數為 n, 報數到 m 的人就自殺。則剛開始的編號為

…
1
…
m - 2

m - 1

m

m + 1

m + 2
…
n
…

進行了一次刪除之后，刪除了編號為 m 的節點。刪除之后，就只剩下 n - 1 個節點了，刪除前和刪除之后的編號轉換關系為：

刪除前     ---     刪除后

…          ---      …

m - 2     ---     n - 2

m - 1    ---      n - 1

m         ----    無(因為編號被刪除了)

m + 1     ---     1(因為下次就從這里報數了)

m + 2     ----     2

…         ----         …

新的環中只有 n - 1 個節點。且刪除前編號為 m + 1, m + 2, m + 3 的節點成了刪除后編號為 1， 2， 3 的節點。

假設 old 為刪除之前的節點編號， new 為刪除了一個節點之后的編號，則 old 與 new 之間的關系為 old = (new + m - 1) % n + 1。

這樣，我們就得出 f(n, m) 與 f(n - 1, m)之間的關系了，而 f(1, m) = 1.所以我們可以采用遞歸的方式來做。代碼如下：

int f(int n, int m){
    if(n == 1)   return n;
    return (f(n - 1, m) + m - 1) % n + 1;
}

怎么不是一行而是兩行？如果你經常刷題，那肯定希望自己的代碼看起來越短越簡介越好，至于會不會變的更難理解？我懶的理，所以代碼如下

int f(int n, int m){
    return n == 1 ? n : (f(n - 1, m) + m - 1) % n + 1;
}

當然，我之前寫過一篇文章，用了三種方法來解決約瑟夫環，感興趣的也可以看：記一道阿里筆試題：我是如何用一行代碼解決約瑟夫環問題的

三、只出現一次的數

問題描述：給你一個整型數組，數組中有一個數只出現過一次，其他數都出現了兩次，求這個只出現了一次的數。

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

然而這道題其實可以采用異或運算來解決，兩個相同的數異或的結果是 0，一個數和 0 異或的結果是它本身，并且異或運算支持交換律，基于這個特點，我們只需要把這一組整型全部異或一下，最后的結果就是我們要找的數了。

例如這組數據是：1， 2， 3， 4， 5， 1， 2， 3， 4。其中 5 只出現了一次，其他都出現了兩次，把他們全部異或一下，結果如下：

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

1^2^3^4^5^1^2^3^4 = （1^1)^(2^2)^(3^3)^(4^4)^5= 0^0^0^0^5 = 5。

通過這種方法，可以把空間復雜度降低到 O(1)，而時間復雜度不變，相應的代碼如下

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

一行代碼解決方案如下：

// 例如使用這個函數的時候，我們最開始傳給 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]);
}

四、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 整除的數有多少個。

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);
}