日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時間：8:30-17:00
你可能遇到了下面的問題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
太透徹了：約瑟夫環(huán)的三種解法

[[391962]]

本文轉(zhuǎn)載自微信公眾號「bigsai」，作者bigsai。轉(zhuǎn)載本文請聯(lián)系bigsai公眾號。

前言

約瑟夫環(huán)問題是算法中相當(dāng)經(jīng)典的一個問題，其問題理解是相當(dāng)容易的，并且問題描述有非常多的版本，并且約瑟夫環(huán)問題還有很多變形，這篇約瑟夫問題的講解，一定可以帶你理解通通!

什么是約瑟夫環(huán)問題?

約瑟夫環(huán)問題在不同平臺被"優(yōu)化"描述的不一樣，例如在?？蛣χ竜ffer叫孩子們的游戲，還有叫殺人游戲，點名……最直接的感覺還是力扣上劍指offer62的描述：圓圈中最后剩下的數(shù)字。

問題描述：

0,1,···,n-1這n個數(shù)字排成一個圓圈，從數(shù)字0開始，每次從這個圓圈里刪除第m個數(shù)字(刪除后從下一個數(shù)字開始計數(shù))。求出這個圓圈里剩下的最后一個數(shù)字。

例如，0、1、2、3、4這5個數(shù)字組成一個圓圈，從數(shù)字0開始每次刪除第3個數(shù)字，則刪除的前4個數(shù)字依次是2、0、4、1，因此最后剩下的數(shù)字是3。

當(dāng)然，這里考慮m，n都是正常的數(shù)據(jù)范圍，其中

  • 1 <= n <= 10^5
  • 1 <= m <= 10^6

對于這個問題，你可能腦海中有了印象，想著小時候村里一群孩子坐在一起，從某個開始報數(shù)然后數(shù)到幾出列，下一個重新開始一直到最后一個。不同人用不同方法解決，青銅直接模擬，鉆石會優(yōu)化一下，王者用公式，下面詳細(xì)給大家講解思路。

循環(huán)鏈表模擬

這個問題最本質(zhì)其實就是循環(huán)鏈表的問題，圍成一個圈之后，就沒有結(jié)尾這就是一個典型的循環(huán)鏈表嘛!一個一個順序報數(shù)，那不就是鏈表的遍歷枚舉嘛!數(shù)到對應(yīng)數(shù)字的出列，這不就是循環(huán)鏈表的刪除嘛!

鏈表模擬

并且這里還有非常方便的地方：

  • 循環(huán)鏈表的向下枚舉不需要考慮頭尾問題，直接node=node.next向下
  • 循環(huán)鏈表的刪除也不需要考慮頭尾問題，直接node.next=node.next.next刪除

當(dāng)然也有一些需要注意的地方

  • 形成環(huán)形鏈表很簡單，只需要將普通鏈表的最后一個節(jié)點的next指向第一個節(jié)點即可
  • 循環(huán)鏈表中只有一個節(jié)點的時候停止返回，即node.next=node的時候
  • 刪除，需要找到待刪除的前面節(jié)點，所以我們刪除計數(shù)的時候要少計一位，利用前面的那個節(jié)點直接刪除后面節(jié)點即可

這樣，思路明確，直接開擼代碼：

 
 
 
 
    
  
  
  
  
  1. class Solution { 
    2. 
  
  
  
  
  2.     class node//鏈表節(jié)點 
    3. 
  
  
  
  
  3.     { 
    4. 
  
  
  
  
  4.         int val; 
    5. 
  
  
  
  
  5.         public node(int value) { 
    6. 
  
  
  
  
  6.             this.val=value; 
    7. 
  
  
  
  
  7.         } 
    8. 
  
  
  
  
  8.         node next; 
    9. 
  
  
  
  
  9.     } 
    10. 
  
  
  
  
  10.     public int lastRemaining(int n, int m) { 
    11. 
  
  
  
  
  11.         if(m==1)return n-1;//一次一個直接返回最后一個即可 
    12. 
  
  
  
  
  12.         node head=new node(0); 
    13. 
  
  
  
  
  13.         node team=head;//創(chuàng)建一個鏈表 
    14. 
  
  
  
  
  14.         for(int i=1;i
  
  
  
  
  15.         { 
    16. 
  
  
  
  
  16.             team.next=new node(i); 
    17. 
  
  
  
  
  17.             team=team.next; 
    18. 
  
  
  
  
  18.         } 
    19. 
  
  
  
  
  19.         team.next=head;//使形成環(huán) 
    20. 
  
  
  
  
  20.         int index=0;//從0開始計數(shù) 
    21. 
  
  
  
  
  21.         while (head.next!=head) {//當(dāng)剩余節(jié)點不止一個的時候 
    22. 
  
  
  
  
  22.             //如果index=m-2 那就說明下個節(jié)點(m-1)該刪除了 
    23. 
  
  
  
  
  23.             if(index==m-2) 
    24. 
  
  
  
  
  24.             { 
    25. 
  
  
  
  
  25.                 head.next=head.next.next; 
    26. 
  
  
  
  
  26.                 index=0; 
    27. 
  
  
  
  
  27.             } 
    28. 
  
  
  
  
  28.             else { 
    29. 
  
  
  
  
  29.                 index++; 
    30. 
  
  
  
  
  30.             } 
    31. 
  
  
  
  
  31.             head=head.next; 
    32. 
  
  
  
  
  32.         } 
    33. 
  
  
  
  
  33.         return head.val; 
    34. 
  
  
  
  
  34.     } 
    35. 
  
  
  
  
  35. } 
    36.

當(dāng)然，這種算法太復(fù)雜了，大部分的OJ你提交上去是無法AC的，因為超時太嚴(yán)重了，具體的我們可以下面分析。

有序集合模擬

上面使用鏈表直接模擬游戲過程會造成非常嚴(yán)重非常嚴(yán)重的超時，n個數(shù)字，數(shù)到第m個出列。因為m如果非常大遠(yuǎn)遠(yuǎn)大于m，那么將進行很多次轉(zhuǎn)圈圈。

所以我們可以利用求余的方法判斷等價最低的枚舉次數(shù)，然后將其刪除即可，在這里你可以繼續(xù)使用自建鏈表去模擬，上面的while循環(huán)以及上面只需添加一個記錄長度的每次求余算圈數(shù)即可：

 
 
 
 
    
  
  
  
  
  1. int len=n; 
    2. 
  
  
  
  
  2. while (head.next!=head) { 
    3. 
  
  
  
  
  3.   if(index==(m-2)%len) 
    4. 
  
  
  
  
  4.   { 
    5. 
  
  
  
  
  5.     head.next=head.next.next; 
    6. 
  
  
  
  
  6.     index=0; 
    7. 
  
  
  
  
  7.     len--; 
    8. 
  
  
  
  
  8.   } 
    9. 
  
  
  
  
  9.   else { 
    10. 
  
  
  
  
  10.     index++; 
    11. 
  
  
  
  
  11.   } 
    12. 
  
  
  
  
  12.   head=head.next; 
    13. 
  
  
  
  
  13. } 
    14.

但我們很多時候不會手動去寫一個鏈表模擬，我們會借助ArrayList和LinkedList去模擬，如果使用LinkedList其底層也是鏈表，使用ArrayList的話其底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組。不過在使用List其代碼方法一致。

List可以直接知道長度，也可刪除元素，使用List的難點是一個順序表怎么模擬成循環(huán)鏈表?

咱們仔細(xì)思考：假設(shè)當(dāng)前長度為n，數(shù)到第m個(通過上面分析可以求余讓這個有效的m%n不大于n)刪除，在index位置刪除。那么刪除后剩下的就是n-1長度，index位置就是表示第一個計數(shù)的位置，我們可以通過求余得知走下一個刪除需要多少步，那么下個位置怎么確定呢?

刪除3號下標(biāo)

你可以分類討論看看走的次數(shù)是否越界，但這里有更巧妙的方法，可以直接求的下一次具體的位置，公式就是為：

 
 
 
 
    
  
  
  
  
  1. index=(index+m-1)%(list.size()); 
    2.

因為index是從1計數(shù)，如果是循環(huán)的再往前m-1個就是真正的位置，但是這里可以先假設(shè)先將這個有序集合的長度擴大若干倍，然后從index計數(shù)開始找到假設(shè)不循環(huán)的位置index2，最后我們將這個位置index2%(集合長度)即為真正的長度。

真實位置計算

使用這個公式一舉幾得，既能把上面m過大循環(huán)過多的情況解決，又能找到真實的位置，就是將這個環(huán)先假設(shè)成線性的然后再去找到真的位置，如果不理解的話可以再看看這個圖：

這種情況的話大部分的OJ是可以勉強過關(guān)的，面試官的層面也大概率差不多的，具體代碼為：

 
 
 
 
    
  
  
  
  
  1. class Solution { 
    2. 
  
  
  
  
  2.     public int lastRemaining(int n, int m) { 
    3. 
  
  
  
  
  3.         if(m==1) 
    4. 
  
  
  
  
  4.             return n-1; 
    5. 
  
  
  
  
  5.         Listlist=new ArrayList<>(); 
    6. 
  
  
  
  
  6.         for(int i=0;i
  
  
  
  
  7.         { 
    8. 
  
  
  
  
  8.             list.add(i); 
    9. 
  
  
  
  
  9.         } 
    10. 
  
  
  
  
  10.         int index=0; 
    11. 
  
  
  
  
  11.         while (list.size()>1) 
    12. 
  
  
  
  
  12.         { 
    13. 
  
  
  
  
  13.             index=(index+m-1)%(list.size()); 
    14. 
  
  
  
  
  14.             list.remove(index); 
    15. 
  
  
  
  
  15.         } 
    16. 
  
  
  
  
  16.         return list.get(0); 
    17. 
  
  
  
  
  17.     } 
    18. 
  
  
  
  
  18. } 
    19.

遞歸公式解決

我們回顧上面的優(yōu)化過程，上面用求余可以解決m比n大很多很多的情況(即理論上需要轉(zhuǎn)很多很多圈的情況)。但是還可能存在n本身就很大的情況，無論是順序表ArrayList還是鏈表LinkedList去頻繁查詢、刪除都是很低效的。

所以聰明的人就開始從數(shù)據(jù)找一些規(guī)律或者關(guān)系。

先拋出公式：

 
 
 
 
    
  
  
  
  
  1. f(n,m)=(f(n-1,m)+m)%n 
    2. 
  
  
  
  
  2. f(n,m)指n個人，報第m個編號出列最終編號 
    3.

下面要認(rèn)真看一下我的分析過程：

我們舉個例子，有0 1 2 3 4 5 6 7 8 9十個數(shù)字，假設(shè)m為3,最后結(jié)果可以先記成f(10,3)，即使我們不知道它是多少。

當(dāng)進行第一次時候，找到元素2 刪除，此時還剩9個元素，但起始位置已經(jīng)變成元素3。等價成3 4 5 6 7 8 9 0 1這9個數(shù)字重寫開始找。

f(10,3)刪除第一個數(shù)

此時這個序列最終剩下的一個值即為f(10,3)，這個序列的值和f(9,3)不同，但是都是9個數(shù)且m等于3，所以其刪除位置是相同的，即算法大體流程是一致的，只是各位置上的數(shù)字不一樣。所以我們需要做的事情是找找這個序列上和f(9,3)值上有沒有什么聯(lián)系。

尋找過程中別忘記兩點，首先可通過%符號對數(shù)字有效擴充，即我們可以將3 4 5 6 7 8 9 0 1這個序列看成(3,4,5,6,7,8,9,10,11)%10.這里的10即為此時的n數(shù)值。

另外數(shù)值如果是連續(xù)的，那么最終一個結(jié)果的話是可以找到聯(lián)系的(差值為一個定制)。所以我們可以就找到f(10,3)和f(9,3)值之間結(jié)果的關(guān)系，可以看下圖：

f(10,3)刪除一次和f(9,3)

所以f(10,3)的結(jié)果就可以轉(zhuǎn)化為f(9,3)的表達(dá),后面也是同理：

 
 
 
 
    
  
  
  
  
  1. f(10,3)=(f(9,3)+3)%10 
    2. 
  
  
  
  
  2. f(9,3)=(f(8,3)+3)%9 
    3. 
  
  
  
  
  3. …… 
    4. 
  
  
  
  
  4. f(2,3)=(f(1,3)+3)%2 
    5. 
  
  
  
  
  5. f(1,3)=0 
    6.

這樣，我們就不用模擬操作，可以直接從數(shù)值的關(guān)系找到遞推的關(guān)系，可以輕輕松松的寫下代碼：

 
 
 
 
    
  
  
  
  
  1. class Solution { 
    2. 
  
  
  
  
  2.     int index=0; 
    3. 
  
  
  
  
  3.     public int lastRemaining(int n, int m) { 
    4. 
  
  
  
  
  4.          if(n==1) 
    5. 
  
  
  
  
  5.             return 0;       
    6. 
  
  
  
  
  6.         return (lastRemaining(n-1,m)+m)%n; 
    7. 
  
  
  
  
  7.     } 
    8. 
  
  
  
  
  8. } 
    9.

但是遞歸效率因為有個來回的規(guī)程，效率相比直接迭代差一些，也可從前往后迭代：

 
 
 
 
    
  
  
  
  
  1. class Solution { 
    2. 
  
  
  
  
  2.     public int lastRemaining(int n, int m) { 
    3. 
  
  
  
  
  3.         int value=0; 
    4. 
  
  
  
  
  4.             for(int i=1;i<=n;i++) 
    5. 
  
  
  
  
  5.             { 
    6. 
  
  
  
  
  6.                 value=(value+m)%i; 
    7. 
  
  
  
  
  7.             } 
    8. 
  
  
  
  
  8.             return  value; 
    9. 
  
  
  
  
  9.     } 
    10. 
  
  
  
  
  10. } 
    11.

結(jié)語

我想，通過本篇文章你應(yīng)該掌握和理解了約瑟夫環(huán)問題，這種裸的約瑟夫環(huán)問題出現(xiàn)的概率很大，考察很頻繁，鏈表模擬是根本思想，有序集合模擬鏈表是提升，而公式遞推才是最有學(xué)習(xí)價值的地方，如果你剛開始接觸不理解可以多看幾遍。如果能用公式遞推給面試官說兩句，講講原理，那一定會讓面試官眼前一亮的!


網(wǎng)頁標(biāo)題：太透徹了：約瑟夫環(huán)的三種解法
分享地址：http://www.5511xx.com/article/cocjjic.html