一、2 的冪次方
判斷一個整數(shù) n 是否為 2 的冪次方

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

創(chuàng)新互聯(lián)主要從事網(wǎng)站制作、網(wǎng)站建設(shè)、網(wǎng)頁設(shè)計、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)桑日,10余年網(wǎng)站建設(shè)經(jīng)驗,價格優(yōu)惠、服務(wù)專業(yè),歡迎來電咨詢建站服務(wù):13518219792

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

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

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

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

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

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

二、約瑟夫環(huán)實現(xiàn)

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

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

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

原理是這樣的：

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

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

…
1
…
m - 2

m - 1

m

m + 1

m + 2
…
n
…

進(jìn)行了一次刪除之后，刪除了編號為 m 的節(jié)點。刪除之后，就只剩下 n - 1 個節(jié)點了，刪除前和刪除之后的編號轉(zhuǎn)換關(guān)系為：

刪除前     ---     刪除后

…          ---      …

m - 2     ---     n - 2

m - 1    ---      n - 1

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

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

m + 2     ----     2

…         ----         …

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

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

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

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

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

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

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

三、只出現(xiàn)一次的數(shù)

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

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

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

例如這組數(shù)據(jù)是：1， 2， 3， 4， 5， 1， 2， 3， 4。其中 5 只出現(xiàn)了一次，其他都出現(xiàn)了兩次，把他們?nèi)慨惢蛞幌?，結(jié)果如下：

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

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

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

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

一行代碼解決方案如下：

// 例如使用這個函數(shù)的時候，我們最開始傳給 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 的階乘

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

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

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

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

答是可以的，并且只有 2 * 5  才會產(chǎn)生 10。

注意，4 * 5 = 20 也能產(chǎn)生 0 啊，不過我們也可以把 20 進(jìn)行分解啊，20 = 10 * 2。

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

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

然而進(jìn)一步拆解，我們發(fā)現(xiàn)

當(dāng) N = 20 時，1~20 可以產(chǎn)生幾個 5 ？答是 4 個，此時有 N / 5 = 4。

當(dāng) N = 24 時，1~24 可以產(chǎn)生幾個 5 ？答是 4 個，此時有 N / 5 = 4。

當(dāng) N = 25 時，1~25 可以產(chǎn)生幾個 5？答是 6 個，主要是因為 25 貢獻(xiàn)了兩個 5，此時有 N / 5 + N / 5^2 = 6。

…

可以發(fā)現(xiàn) 產(chǎn)生 5 的個數(shù)為 sum = N/5 + N/5^2 + N/5^3+….

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

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

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)建站www.cdcxhl.com，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機、免備案服務(wù)器”等云主機租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

本文名稱：java算法題目及答案介紹-創(chuàng)新互聯(lián)
轉(zhuǎn)載源于：http://weahome.cn/article/dhhdpc.html