題目描述
每年六一兒童節,牛客都會準備一些小禮物去看望孤兒院的小朋友,今年亦是如此，HF作為牛客的資深元老,自然也準備了一些小游戲，其中,有個游戲是這樣的:首先,讓小朋友們圍成一個大圈，然后,他隨機指定一個數m,讓編號為0的小朋友開始報數，每次喊到m-1的那個小朋友要出列唱首歌,然后可以在禮品箱中任意的挑選禮物,并且不再回到圈中,從他的下一個小朋友開始,繼續0…m-1報數…這樣下去…直到剩下最后一個小朋友,可以不用表演,并且拿到牛客名貴的“名偵探柯南”典藏版(名額有限哦!!_)，請你試著想下,哪個小朋友會得到這份禮品呢？(注：小朋友的編號是從0到n-1)
如果沒有小朋友，請回傳-1
題目抽象：給定一個由[0…n-1]構成的陣列，第一次從0開始數m個數，然后洗掉，以后每次都從洗掉的數下一個位置開始數m個數，然后洗掉，直到剩余一個數字，找出那個數字，
比如：arr = [0 1 2 3 4]， m = 3
第一次：洗掉2 ，變成 arr = [0 1 3 4]
第二次，洗掉0，變成 arr = [1 3 4]
第三次，洗掉4，變成 arr = [1 3]
第四次，洗掉1，變成 arr = [3]
題目描述大致程序如圖所示：
輸入輸出示例
輸入：5,3
輸出：3
代碼示例
# -*- coding:utf-8 -*-
class Solution:
def LastRemaining_Solution(self, n, m):
# write code here
# 考慮沒有小朋友的情況
if n < 1:
return -1
# 只有一個小朋友，直接回傳其下標0
if n == 1:
return 0
# 兩個及以上的小朋友
value = 0
for index in range(2, n+1):
# 迭代公式計算
value = (value + m) % index
return value
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/286483.html
標籤：其他