尋找循環遊戲的獲勝者

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中文網其他相關文章！