寻找循环游戏的获胜者

1823。寻找循环游戏的获胜者

中

有 n 个好友正在玩游戏。朋友们围坐成一圈，并按顺时针顺序从1到n编号。更正式地说，从第 i^th 个朋友顺时针移动，您将到达第 (i+1)^th 个朋友，其中 1 n，从第 n第 ^{个朋友顺时针移动，您将到达第 1 个}第

个朋友。

游戏规则如下：

1. 从第一个^第朋友开始
。
2. 按顺时针方向数出接下来的 k 个朋友包括
您开始的朋友。计数会绕一圈，可能会多次计数一些朋友。
您数到的最后一个朋友离开圈子并输掉游戏。
4. 如果圈子里还有多个朋友，请返回第2步从刚失去的朋友的顺时针开始
并重复。
否则，圈子里的最后一个朋友就赢得了游戏。

给定朋友的数量 n 和整数 k，返回游戏的获胜者

。

示例1：

• 输入：
n = 5，k = 2
• 输出：
3
• 说明：
  以下是游戏步骤：
  从朋友 1 开始。
  顺时针数出2个朋友，分别是朋友1和2。
  好友 2 离开圈子。下一个开始的是朋友 3。
  顺时针数2个朋友，分别是朋友3和4。
  好友 4 离开圈子。下一个开始的是朋友5。
  顺时针数出2个朋友，分别是朋友5和1。
  好友 1 离开圈子。下一个开始的是朋友 3。
  顺时针数2个朋友，分别是朋友3和朋友5。
  好友 5 离开圈子。只剩下朋友 3，所以他们是获胜者。

示例2：

• 输入：
n = 6，k = 5
• 输出：
1
• 说明：
朋友们按顺序离开：5、4、6、2、3。获胜者是朋友 1。

约束：

1

跟进：

你能在空间恒定的线性时间内解决这个问题吗？

解决方案：

class Solution {

    /**
     * @param Integer $n
     * @param Integer $k
     * @return Integer
     */
    function findTheWinner($n, $k) {
        $winner = 0;
        for ($i = 1; $i <= $n; $i++) {
            $winner = ($winner + $k) % $i;
        }
        return $winner + 1; // +1 because array index starts from 0
    }
}

联系链接

• 领英
• GitHub

以上是寻找循环游戏的获胜者的详细内容。更多信息请关注PHP中文网其他相关文章！