這篇文章主要介紹“約瑟夫環(huán)的解法有哪些”，在日常操作中，相信很多人在約瑟夫環(huán)的解法有哪些問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”約瑟夫環(huán)的解法有哪些”的疑惑有所幫助！接下來，請跟著小編一起來學(xué)習(xí)吧！

創(chuàng)新互聯(lián)公司于2013年開始，公司以成都做網(wǎng)站、網(wǎng)站制作、系統(tǒng)開發(fā)、網(wǎng)絡(luò)推廣、文化傳媒、企業(yè)宣傳、平面廣告設(shè)計(jì)等為主要業(yè)務(wù)，適用行業(yè)近百種。服務(wù)企業(yè)客戶成百上千家，涉及國內(nèi)多個(gè)省份客戶。擁有多年網(wǎng)站建設(shè)開發(fā)經(jīng)驗(yàn)。為企業(yè)提供專業(yè)的網(wǎng)站建設(shè)、創(chuàng)意設(shè)計(jì)、宣傳推廣等服務(wù)。 通過專業(yè)的設(shè)計(jì)、獨(dú)特的風(fēng)格，為不同客戶提供各種風(fēng)格的特色服務(wù)。

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

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

問題描述：

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

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

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

• 1 <= n <= 10^5

• 1 <= m <= 10^6

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

循環(huán)鏈表模擬

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

鏈表模擬

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

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

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

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

• 形成環(huán)形鏈表很簡單，只需要將普通鏈表的最后一個(gè)節(jié)點(diǎn)的next指向第一個(gè)節(jié)點(diǎn)即可

• 循環(huán)鏈表中只有一個(gè)節(jié)點(diǎn)的時(shí)候停止返回，即node.next=node的時(shí)候

• 刪除，需要找到待刪除的前面節(jié)點(diǎn)，所以我們刪除計(jì)數(shù)的時(shí)候要少計(jì)一位，利用前面的那個(gè)節(jié)點(diǎn)直接刪除后面節(jié)點(diǎn)即可

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

class Solution {     class node//鏈表節(jié)點(diǎn)     {         int val;         public node(int value) {             this.val=value;         }         node next;     }     public int lastRemaining(int n, int m) {         if(m==1)return n-1;//一次一個(gè)直接返回最后一個(gè)即可         node head=new node(0);         node team=head;//創(chuàng)建一個(gè)鏈表         for(int i=1;i
當(dāng)然，這種算法太復(fù)雜了，大部分的OJ你提交上去是無法AC的，因?yàn)槌瑫r(shí)太嚴(yán)重了，具體的我們可以下面分析。
有序集合模擬
上面使用鏈表直接模擬游戲過程會造成非常嚴(yán)重非常嚴(yán)重的超時(shí)，n個(gè)數(shù)字，數(shù)到第m個(gè)出列。因?yàn)閙如果非常大遠(yuǎn)遠(yuǎn)大于m，那么將進(jìn)行很多次轉(zhuǎn)圈圈。
所以我們可以利用求余的方法判斷等價(jià)最低的枚舉次數(shù)，然后將其刪除即可，在這里你可以繼續(xù)使用自建鏈表去模擬，上面的while循環(huán)以及上面只需添加一個(gè)記錄長度的每次求余算圈數(shù)即可：
int len=n; while (head.next!=head) {   if(index==(m-2)%len)   {     head.next=head.next.next;     index=0;     len--;   }   else {     index++;   }   head=head.next; }
但我們很多時(shí)候不會手動去寫一個(gè)鏈表模擬，我們會借助ArrayList和LinkedList去模擬，如果使用LinkedList其底層也是鏈表，使用ArrayList的話其底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組。不過在使用List其代碼方法一致。
List可以直接知道長度，也可刪除元素，使用List的難點(diǎn)是一個(gè)順序表怎么模擬成循環(huán)鏈表?
咱們仔細(xì)思考：假設(shè)當(dāng)前長度為n，數(shù)到第m個(gè)(通過上面分析可以求余讓這個(gè)有效的m%n不大于n)刪除，在index位置刪除。那么刪除后剩下的就是n-1長度，index位置就是表示第一個(gè)計(jì)數(shù)的位置，我們可以通過求余得知走下一個(gè)刪除需要多少步，那么下個(gè)位置怎么確定呢?
刪除3號下標(biāo)
你可以分類討論看看走的次數(shù)是否越界，但這里有更巧妙的方法，可以直接求的下一次具體的位置，公式就是為：
index=(index+m-1)%(list.size());
因?yàn)閕ndex是從1計(jì)數(shù)，如果是循環(huán)的再往前m-1個(gè)就是真正的位置，但是這里可以先假設(shè)先將這個(gè)有序集合的長度擴(kuò)大若干倍，然后從index計(jì)數(shù)開始找到假設(shè)不循環(huán)的位置index2，最后我們將這個(gè)位置index2%(集合長度)即為真正的長度。
真實(shí)位置計(jì)算
使用這個(gè)公式一舉幾得，既能把上面m過大循環(huán)過多的情況解決，又能找到真實(shí)的位置，就是將這個(gè)環(huán)先假設(shè)成線性的然后再去找到真的位置，如果不理解的話可以再看看這個(gè)圖：
這種情況的話大部分的OJ是可以勉強(qiáng)過關(guān)的，面試官的層面也大概率差不多的，具體代碼為：
class Solution {     public int lastRemaining(int n, int m) {         if(m==1)             return n-1;         Listlist=new ArrayList<>();         for(int i=0;i1)         {             index=(index+m-1)%(list.size());             list.remove(index);         }         return list.get(0);     } }
遞歸公式解決
我們回顧上面的優(yōu)化過程，上面用求余可以解決m比n大很多很多的情況(即理論上需要轉(zhuǎn)很多很多圈的情況)。但是還可能存在n本身就很大的情況，無論是順序表ArrayList還是鏈表LinkedList去頻繁查詢、刪除都是很低效的。
所以聰明的人就開始從數(shù)據(jù)找一些規(guī)律或者關(guān)系。
先拋出公式：
f(n,m)=(f(n-1,m)+m)%n f(n,m)指n個(gè)人，報(bào)第m個(gè)編號出列最終編號
下面要認(rèn)真看一下我的分析過程：
我們舉個(gè)例子，有0 1 2 3 4 5 6 7 8 9十個(gè)數(shù)字，假設(shè)m為3,最后結(jié)果可以先記成f(10,3)，即使我們不知道它是多少。
當(dāng)進(jìn)行第一次時(shí)候，找到元素2 刪除，此時(shí)還剩9個(gè)元素，但起始位置已經(jīng)變成元素3。等價(jià)成3 4 5 6 7 8 9 0 1這9個(gè)數(shù)字重寫開始找。
f(10,3)刪除第一個(gè)數(shù)
此時(shí)這個(gè)序列最終剩下的一個(gè)值即為f(10,3)，這個(gè)序列的值和f(9,3)不同，但是都是9個(gè)數(shù)且m等于3，所以其刪除位置是相同的，即算法大體流程是一致的，只是各位置上的數(shù)字不一樣。所以我們需要做的事情是找找這個(gè)序列上和f(9,3)值上有沒有什么聯(lián)系。
尋找過程中別忘記兩點(diǎn)，首先可通過%符號對數(shù)字有效擴(kuò)充，即我們可以將3 4 5 6 7 8 9 0  1這個(gè)序列看成(3,4,5,6,7,8,9,10,11)%10.這里的10即為此時(shí)的n數(shù)值。
另外數(shù)值如果是連續(xù)的，那么最終一個(gè)結(jié)果的話是可以找到聯(lián)系的(差值為一個(gè)定制)。所以我們可以就找到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á),后面也是同理：
f(10,3)=(f(9,3)+3)%10 f(9,3)=(f(8,3)+3)%9 …… f(2,3)=(f(1,3)+3)%2 f(1,3)=0
這樣，我們就不用模擬操作，可以直接從數(shù)值的關(guān)系找到遞推的關(guān)系，可以輕輕松松的寫下代碼：
class Solution {     int index=0;     public int lastRemaining(int n, int m) {          if(n==1)             return 0;               return (lastRemaining(n-1,m)+m)%n;     } }
但是遞歸效率因?yàn)橛袀€(gè)來回的規(guī)程，效率相比直接迭代差一些，也可從前往后迭代：
class Solution {     public int lastRemaining(int n, int m) {         int value=0;             for(int i=1;i<=n;i++)             {                 value=(value+m)%i;             }             return  value;     } }
到此，關(guān)于“約瑟夫環(huán)的解法有哪些”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識，請繼續(xù)關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編會繼續(xù)努力為大家?guī)砀鄬?shí)用的文章！
            
            
                        

            網(wǎng)站名稱：約瑟夫環(huán)的解法有哪些            

            URL網(wǎng)址：http://weahome.cn/article/pdsjds.html