一行代碼居然能解決這么多曾經(jīng)困擾我的算法題-創(chuàng)新互聯(lián)

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

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

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

一、2 的冪次方

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

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

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

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

然后我們把 n 和 （n - 1）進行與操作，結(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;
}

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

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

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

問題描述：編號為 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ù)學關(guān)系，我們只需要找出這個關(guān)系即可。

我們定義遞歸函數(shù) f(n，m) 的返回結(jié)果是存活士兵的編號，顯然當 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
…

進行了一次刪除之后，刪除了編號為 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.所以我們可以采用遞歸的方式來做。代碼如下：

注：有些人可能會疑惑為什么不是 old = (new + m ) % n 呢？主要是因為編號是從 1 開始的，而不是從 0 開始的。如果 new + m == n的話，會導致最后的計算結(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)常刷題，那肯定希望自己的代碼看起來越短越簡介越好，至于會不會變的更難理解？我懶的理，所以代碼如下

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

當然，我之前寫過一篇文章，用了三種方法來解決約瑟夫環(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]);
}

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

四、n 的階乘

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

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

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 進行分解啊，20 = 10 * 2。

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

注意，像 25 能夠被 5整除兩次，所以25是能夠產(chǎn)生 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;
}

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

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

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

當 N = 25 時，1~25 可以產(chǎn)生幾個 5？答是 6 個，主要是因為 25 貢獻了兩個 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);
}

總結(jié)

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

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

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

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

廣告

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