Trouvez le gagnant du jeu circulaire

1823. Trouvez le gagnant du jeu circulaire

Moyen

Il y a n amis qui jouent à un jeu. Les amis sont assis en cercle et sont numérotés de 1 à n dans dans l'ordre des aiguilles d'une montre. Plus formellement, se déplacer dans le sens des aiguilles d'une montre à partir du i^ème ami vous amène au (i+1)^ème ami pour 1 <= i < n, et en vous déplaçant dans le sens des aiguilles d'une montre à partir du n^ième ami vous amène au 1^er ami.

Les règles du jeu sont les suivantes :

1. Commencerau 1^erami.
2. Comptez les k amis suivants dans le sens des aiguilles d'une montre y compris l'ami avec lequel vous avez commencé. Le décompte fait le tour du cercle et peut compter certains amis plus d'une fois.
3. Le dernier ami que vous avez compté quitte le cercle et perd la partie.
4. S'il y a encore plus d'un ami dans le cercle, revenez à l'étape 2 en commençant de l'ami immédiatement dans le sens des aiguilles d'une montre de l'ami qui vient de perdre et répétez.
5. Sinon, le dernier ami du cercle remporte la partie.

Étant donné le nombre d'amis, n, et un entier k, renvoyez le gagnant du jeu.

Exemple 1 :

• Entrée : n = 5, k = 2
• Sortie : 3
• Explication : Voici les étapes du jeu :
  1. Commencez par l'ami 1.
  2. Comptez 2 amis dans le sens des aiguilles d'une montre, qui sont les amis 1 et 2.
  3. L'ami 2 quitte le cercle. Le prochain départ est l'ami 3.
  4. Comptez 2 amis dans le sens des aiguilles d'une montre, qui sont les amis 3 et 4.
  5. L'ami 4 quitte le cercle. Le prochain départ est l'ami 5.
  6. Comptez 2 amis dans le sens des aiguilles d'une montre, qui sont les amis 5 et 1.
  7. L'ami 1 quitte le cercle. Le prochain départ est l'ami 3.
  8. Comptez 2 amis dans le sens des aiguilles d'une montre, qui sont les amis 3 et 5.
  9. L'ami 5 quitte le cercle. Il ne reste plus que l'ami 3, il est donc le gagnant.

Exemple 2 :

• Entrée : n = 6, k = 5
• Sortie : 1
• Explication : Les amis partent dans cet ordre : 5, 4, 6, 2, 3. Le gagnant est l'ami 1.

Contraintes :

• 1 <= k <= n <= 500

Suivi :

Pourriez-vous résoudre ce problème en temps linéaire avec un espace constant ?

Solution :

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
    }
}

Liens de contact

• LinkedIn
• GitHub

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!