Python程式：查詢最後拿到氣球的孩子起始索引

假設有n個孩子圍成一個圈，他們等待領取氣球。發放氣球從第k個孩子開始（從索引0開始），發給一個孩子氣球后，該孩子離開圓圈。然後，按照順時針方向，每隔k個孩子就發放一個氣球，直到只剩下一個孩子領取氣球。所以，如果已知n和k，我們需要找到最後拿到氣球的孩子起始索引。

例如，如果輸入n = 3，k = 2，則輸出為1。第一輪，孩子2拿到氣球並離開，圓圈變為[0, 1]。第二輪，孩子0拿到氣球，圓圈變為[1]。

為了解決這個問題，我們將遵循以下步驟：

• arr := 建立一個從0到n的列表

• init := 0

• 當arr的長度大於1時，執行：

  • remove := (init + k) mod arr的長度

  • 刪除arr[remove]

  • init := remove

• 返回arr[0]

讓我們看下面的實現來更好地理解。

示例

 線上演示

class Solution:
   def solve(self, n, k):
      arr = list(range(0, n))
      init = 0
      while len(arr) > 1:
         remove = (init + k) % len(arr)
         del arr[remove]
         init = remove
      return arr[0]

ob = Solution()
n = 3
k = 2
print(ob.solve(n, k))

輸入

3,2

輸出

1

Arnab Chakraborty

更新於: 2020年11月10日

63 次瀏覽

啟動您的職業生涯

完成課程獲得認證

開始學習