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

更新于: 2020年11月10日

63 次浏览

启动您的职业生涯

完成课程获得认证

开始学习
广告