有史以來(lái)最長(zhǎng)的春節(jié)假期，宅在家里干啥最好？當(dāng)然是折騰一些算法題了，下面給大家講幾道一行代碼就能解決的算法題，當(dāng)然，我相信這些算法題你都做過，不過就算做過，也是可以看一看滴，畢竟，你當(dāng)初大概率不是一行代碼解決的。

發(fā)展壯大離不開廣大客戶長(zhǎng)期以來(lái)的信賴與支持，我們將始終秉承“誠(chéng)信為本、服務(wù)至上”的服務(wù)理念，堅(jiān)持“二合一”的優(yōu)良服務(wù)模式，真誠(chéng)服務(wù)每家企業(yè)，認(rèn)真做好每個(gè)細(xì)節(jié)，不斷完善自我，成就企業(yè)，實(shí)現(xiàn)共贏。行業(yè)涉及隧道混凝土攪拌車等，在成都網(wǎng)站建設(shè)公司、成都全網(wǎng)營(yíng)銷推廣、WAP手機(jī)網(wǎng)站、VI設(shè)計(jì)、軟件開發(fā)等項(xiàng)目上具有豐富的設(shè)計(jì)經(jīng)驗(yàn)。

學(xué)會(huì)了一行代碼解決，以后遇到面試官問起的話，就可以裝逼了。

一、2 的冪次方

問題描述：判斷一個(gè)整數(shù) n 是否為 2 的冪次方

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

我們可以把 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;
}

二、一行代碼搞定經(jīng)典的約瑟夫環(huán)

約瑟夫環(huán)問題，我相信大家在大一大二的時(shí)候就接觸過了，很多人也都會(huì)拿來(lái)作為環(huán)形鏈表的一個(gè)應(yīng)用，然而環(huán)形鏈表并非最優(yōu)的解決方法，今天我就用一行代碼干掉它，并且?guī)缀跛闶亲顑?yōu)解了。

鑒于有些人把這道題忘了，我還是把這道題的描述貼出來(lái)一下吧

問題描述：編號(hào)為 1-N 的 N 個(gè)士兵圍坐在一起形成一個(gè)圓圈，從編號(hào)為 1 的士兵開始依次報(bào)數(shù)（1，2，3…這樣依次報(bào)），數(shù)到 m 的 士兵會(huì)被殺死出列，之后的士兵再?gòu)?1 開始報(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 的人就自殺。則剛開始的編號(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)做。代碼如下：

注：有些人可能會(huì)疑惑為什么不是 old = (new + m ) % n 呢？主要是因?yàn)榫幪?hào)是從 1 開始的，而不是從 0 開始的。如果 new + m == n的話，會(huì)導(dǎo)致最后的計(jì)算結(jié)果為 old = 0。所以 old = (new + m - 1) % n + 1.

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)然，我之前寫過一篇文章，用了三種方法來(lái)解決約瑟夫環(huán)，感興趣的也可以看：記一道阿里筆試題：我是如何用一行代碼解決約瑟夫環(huán)問題的

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

問題描述：給你一個(gè)整型數(shù)組，數(shù)組中有一個(gè)數(shù)只出現(xiàn)過一次，其他數(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。

通過這種方法，可以把空間復(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;
}

說(shuō)好的一行代碼的呢？

這不是為了先讓你看的懂嗎？一行代碼解決方案如下：

//?例如使用這個(gè)函數(shù)的時(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]);
}

實(shí)不相瞞，這道題用了一行代碼之后，更加復(fù)雜 + 難懂了，，，，，，不好意思，我錯(cuò)了，不該把簡(jiǎn)單的問題搞復(fù)雜了再扔給面試題的。

四、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)溢出問題，并且時(shí)間復(fù)雜度還大，我們不妨從另一個(gè)思路下手：一個(gè)數(shù)乘以 10 就一定會(huì)在末尾產(chǎn)生一個(gè)零，那么，我們是否可以從哪些數(shù)相乘能夠得到 10?入手呢？

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

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

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

注意，像 25 能夠被 5整除兩次，所以25是能夠產(chǎn)生 2 對(duì) 2 * 5滴。有了這個(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);
}

總結(jié)

有木覺得很牛逼？以后面試官問你這些題，你就把這行代碼扔給他！！！

關(guān)注微信公眾號(hào)【程序員生活志】不錯(cuò)過一件互聯(lián)網(wǎng)新鮮事兒

分享題目：一行代碼居然能解決這么多曾經(jīng)困擾我的算法題-創(chuàng)新互聯(lián)
瀏覽地址：http://vcdvsql.cn/article12/ejdgc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供用戶體驗(yàn)、外貿(mào)網(wǎng)站建設(shè)、品牌網(wǎng)站設(shè)計(jì)、定制網(wǎng)站、關(guān)鍵詞優(yōu)化、小程序開發(fā)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(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)