循環ゲームの勝者を見つける

1823年。循環ゲームの勝者を見つけよう

中

ゲームをプレイしている友達が n 人います。友達は輪になって座っており、時計回りに 1 から n までの番号が付けられています。より正式には、i ^番目 の友人から時計回りに移動すると、(i+1) ^番目 の友人に 1 <= i < で移動します。 n、n^番目の友人から時計回りに移動すると、1^番目の友人に移動します。

ゲームのルールは次のとおりです:

1. 最初の^友達から始めます。
2. 時計回りに次の k 人の友達を数えます。最初の友達も含めて。カウントは円を一周し、一部の友達は複数回カウントされる場合があります。
3. 最後に数えた友達がサークルから離れ、ゲームに負けます。
4. サークル内にまだ複数の友達がいる場合は、負けた友達のすぐ時計回りから手順 2に戻ってを繰り返します。
5. そうでない場合は、サークル内の最後の友達がゲームに勝ちます。

友達の数 n と整数 k を指定すると、ゲームの勝者を返します。

例 1:

• 入力: n = 5、k = 2
• 出力: 3
• 説明: ゲームの手順は次のとおりです。
  1. 友人 1 から開始します。
  2. 時計回りに友達を 2 人数えます。これは友達 1 と友達 2 です。
  3. 友達 2 がサークルから退出しました。次の開始はフレンド 3 です。
  4. 時計回りに友達を 2 人数えます。これは友達 3 と友達 4 です。
  5. 友達 4 がサークルから退出します。次の開始はフレンド 5 です。
  6. 時計回りに友達を 2 人数えます。つまり、友達 5 と友達 1 です。
  7. 友達 1 がサークルから退出しました。次の開始はフレンド 3 です。
  8. 時計回りに友達を 2 人数えます。つまり、友達 3 と友達 5 です。
  9. 友達 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
    }
}

連絡先リンク

• LinkedIn
• GitHub

以上が循環ゲームの勝者を見つけるの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。