【題目】每年六一兒童節(jié),牛客都會(huì)準(zhǔn)備一些小禮物去看望孤兒院的小朋友,今年亦是如此梢夯。HF作為懦阉ⅲ客的資深元老,自然也準(zhǔn)備了一些小游戲。其中,有個(gè)游戲是這樣的:首先,讓小朋友們圍成一個(gè)大圈沿量。然后,他隨機(jī)指定一個(gè)數(shù)m,讓編號(hào)為0的小朋友開(kāi)始報(bào)數(shù)。每次喊到m-1的那個(gè)小朋友要出列唱首歌,然后可以在禮品箱中任意的挑選禮物,并且不再回到圈中,從他的下一個(gè)小朋友開(kāi)始,繼續(xù)0...m-1報(bào)數(shù)....這樣下去....直到剩下最后一個(gè)小朋友,可以不用表演,并且拿到旁┚＃客名貴的“名偵探柯南”典藏版(名額有限哦!!_)朴则。請(qǐng)你試著想下,哪個(gè)小朋友會(huì)得到這份禮品呢？(注：小朋友的編號(hào)是從0到n-1)
【思路】每次刪除的數(shù)的小標(biāo)為(m-1)%len(num)钓简，刪除一個(gè)后乌妒，則后面的節(jié)點(diǎn)變成了頭節(jié)點(diǎn)
【代碼】
class Solution:
def LastRemaining_Solution(self, n, m):
# write code here
if n<=0:
return -1#判斷異常輸入
num = list(range(n))
while len(num)>1:
lucky = (m-1)%len(num)
num = num[lucky+1:]+num[:lucky]
return num[0]
【思路2】
首先我們定義一個(gè)關(guān)于 n 和 m 的方程町磯時(shí)，表示每次在 n 個(gè)數(shù)字 0外邓，1撤蚊， … ，n-1中每次刪除第 m 個(gè)數(shù)字最后剩下的數(shù)字损话。
在這 n個(gè)數(shù)字中侦啸， 第一個(gè)被刪除的數(shù)字是(m-1)%n。為了簡(jiǎn)單起見(jiàn)丧枪，我們把(m- 1)%n 記為 k光涂，那么刪除k之后剩下的 n-1 個(gè)數(shù)字為 0，1拧烦，… 忘闻，k-1，k+1恋博，… 齐佳，n-1私恬，并且下一次刪除從數(shù)字 k+1 開(kāi)始計(jì)數(shù)。相當(dāng)于在剩下的序列中炼吴， k+1 排在最前面本鸣，從而形成 k+1，... 缺厉，n- 1永高，0，I提针，… 命爬，k-1 。該序列最后剩下的數(shù)字也應(yīng)該是關(guān)于 n 和 m 的函數(shù)辐脖。由于這個(gè)序列的規(guī)律和前面最初的序列不一樣（最初的序列是從 0 開(kāi)始的連續(xù)序列）饲宛，因此該函數(shù)不同于前面的函數(shù)，記為 f’(n-1,m)嗜价。最初序列最后剩下的數(shù)字 f(n, m）一定是刪除一個(gè)數(shù)字之后的序列最后剩下的數(shù)字艇抠，即 f(n, m)=f’(n-1, m）。
接下來(lái)我們把剩下的這 n-1 個(gè)數(shù)字的序列 k-1久锥， …家淤，n-1，0瑟由，1絮重，… ，k-1 做一個(gè)映射歹苦，映射的結(jié)果是形成一個(gè)從 0 到 n-2 的序列：
【代碼】
class Solution:
def LastRemaining_Solution(self, n, m):
# write code here
if n<=0:
return -1#判斷異常輸入
last = 0
for i in range(2,n+1):
last = (last+m)%i
return last
