題目描述
年六一兒童節,牛客都會準備一些小禮物去看望孤兒院的小朋友,今年亦是如此。HF作為牛客的資深元老,自然也準備了一些小游戲。其中,有個游戲是這樣的:首先,讓小朋友們圍成一個大圈。然后,他隨機指定一個數m,讓編號為0的小朋友開始報數。每次喊到m-1的那個小朋友要出列唱首歌,然后可以在禮品箱中任意的挑選禮物,并且不再回到圈中,從他的下一個小朋友開始,繼續0…m-1報數…這樣下去…直到剩下最后一個小朋友,可以不用表演,并且拿到牛客名貴的“名偵探柯南”典藏版(名額有限哦!!_)。請你試著想下,哪個小朋友會得到這份禮品呢？(注：小朋友的編號是從0到n-1)
如果沒有小朋友，請返回-1
解題思路
我們注意到，輸入的序列在刪除一個元素后，序列的長度會改變，如果索引(數組下標)
在被刪除的元素位置開始計算，那么每刪除一個元素，序列的長度減一而索引會完全改變。
如果能找到改變前的索引和新索引的對應關系，那么該問題就容易解決了。
我們定義一個函數f(n, m)，表示每次在n個數字0,1,2,3,…,n-1中每次刪除第m個數字后剩下
的數字。那么第一個被刪除的數字的索引是(m-1)%n(例如一共有10個孩子，第五個走，那么走的孩子在數組中的下標為(5-1)%10=4)。
刪除該索引元素后，剩下的n-1個數字
為0,1,2,…,k-1,k+1,…,n-1。下次刪除數字是從k+1位置開始，于是可以把序列看作k+1,..,n-1,0,1,…,k-1。該序列最后剩下的序列也是f的函數。但該函數和第一個函數不同，存在映射關系，使用f’來表示，于是有：f(n, m)=f’(n-1, m)。接下來需要找到映射關系。
給出一個序列，從0～n-1編號。其中，k代表出列的序號的下一個，即k-1出列。
a 0, 1, …, k-1, k, k+1, …, n-1
那么，出列的序號是(m-1)%n，k=m%n（這個可真的是顯而易見）。出列k-1后，序列變為
b 0, 1, …, k-2, k, k+1, …, n-1
然后，我們繼續從n-1后延長這個序列，可以得到
c’ 0, 1, …, k-2, k, k+1, …, n-1, n, n+1, …, n+k-2
我們取從k開始直到n+k-2這段序列。其實這段序列可以看作將序列b的0~k-2段移到了b序列的后面。這樣，得到一個新的序列
c k, k+1, …, n-1, n, n+1, …, n+k-2
好了，整個序列c都減除一個k，得到
d 0, 1, …, n-2
c序列中的n-1, n, n+1都減除個k是什么？這個不需要關心，反正c序列是連續的，我們知道了頭和尾，就能知道d序列是什么樣的。
這樣你看，從序列a到序列d，就是一個n序列到n-1序列的變化，約瑟夫環可以通過遞推來獲得最終結果。ok，繼續向下。
剩下的就是根據n-1序列遞推到n序列。假設在n-1序列中，也就是序列d中，我們知道了最終剩下的一個序號是x
往回推
-
d->c，剛才是同時減了個k，這回再同時加個k，就是x+k；
-
c->b,(x+k)%n。%n以后。k ~ n-1這段序列值不會發生變化，而n~n+k-2這段序列則變成了0～k-2；這兩段序列合起來，就是序列b。
-
x=(x+k)%n。并且，k=m%n，所以x=(x+m%n)%n=(x+m)%n;
-
f[i]=(f[i-1]+m)%i
代碼實現
class Solution {
public:int LastRemaining_Solution(int n, int m){if(n==0)return -1;if(n==1)return 0;return (LastRemaining_Solution(n-1,m)+m)%n;}
};
)
)
)
