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

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

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

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

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

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

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

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

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

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

問(wèn)題描述：編號(hào)為 1-N 的 N 個(gè)士兵圍坐在一起形成一個(gè)圓圈，從編號(hào)為 1 的士兵開(kāi)始依次報(bào)數(shù)（1，2，3…這樣依次報(bào)），數(shù)到 m 的 士兵會(huì)被殺死出列，之后的士兵再?gòu)?1 開(kāi)始報(bào)數(shù)。直到最后剩下一士兵，求這個(gè)士兵的編號(hào)。

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

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

原理是這樣的：

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

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

…
1
…
m - 2

m - 1

m

m + 1

m + 2
…
n
…

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

刪除前     ---     刪除后

…          ---      …

m - 2     ---     n - 2

m - 1    ---      n - 1

m         ----    無(wú)(因?yàn)榫幪?hào)被刪除了)

m + 1     ---     1(因?yàn)橄麓尉蛷倪@里報(bào)數(shù)了)

m + 2     ----     2

…         ----         …

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

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

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

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

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

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

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

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

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

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

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

例如這組數(shù)據(jù)是：1， 2， 3， 4， 5， 1， 2， 3， 4。其中 5 只出現(xiàn)了一次，其他都出現(xiàn)了兩次，把他們?nèi)慨惢蛞幌拢Y(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。

通過(guò)這種方法，可以把空間復(fù)雜度降低到 O(1)，而時(shí)間復(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;
}

一行代碼解決方案如下：

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

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

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

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

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

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

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

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

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 時(shí)，1~20 可以產(chǎn)生幾個(gè) 5 ？答是 4 個(gè)，此時(shí)有 N / 5 = 4。

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

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

…

可以發(fā)現(xiàn) 產(chǎn)生 5 的個(gè)數(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.rwnh.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性?xún)r(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專(zhuān)為企業(yè)上云打造定制，能夠滿足用戶(hù)豐富、多元化的應(yīng)用場(chǎng)景需求。

文章標(biāo)題：java算法題目及答案介紹-創(chuàng)新互聯(lián)
本文路徑：http://www.rwnh.cn/article32/dhhdpc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供標(biāo)簽優(yōu)化、網(wǎng)站建設(shè)、虛擬主機(jī)、外貿(mào)建站、商城網(wǎng)站、微信小程序

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)