Finden Sie den Gewinner des Kreisspiels

1823. Finden Sie den Gewinner des Kreisspiels

Mittel

Es gibt n Freunde, die ein Spiel spielen. Die Freunde sitzen im Kreis und werden im im Uhrzeigersinn von 1 bis n nummeriert. Formeller ausgedrückt führt Sie die Bewegung im Uhrzeigersinn vom i^ten Freund zum (i+1)^ten Freund für 1 <= i < n, und wenn Sie sich im Uhrzeigersinn vom n^ten Freund bewegen, gelangen Sie zum 1^sten Freund.

Die Spielregeln lauten wie folgt:

1. Beginnebeim 1.^.Freund.
2. Zählen Sie die nächsten k Freunde im Uhrzeigersinn einschließlich des Freundes, bei dem Sie angefangen haben. Die Zählung erstreckt sich um den Kreis und kann einige Freunde mehr als einmal zählen.
3. Der letzte Freund, den du gezählt hast, verlässt den Kreis und verliert das Spiel.
4. Wenn sich immer noch mehr als ein Freund im Kreis befindet, gehen Sie zurück zu Schritt 2 beginnen beim Freund unmittelbar im Uhrzeigersinn des Freundes, der gerade verloren hat, und wiederholen Sie den Vorgang.
5. Andernfalls gewinnt der letzte Freund im Kreis das Spiel.

Angesichts der Anzahl der Freunde, n, und einer ganzen Zahl k, gib den Gewinner des Spiels zurück.

Beispiel 1:

• Eingabe: n = 5, k = 2
• Ausgabe: 3
• Erklärung: Hier sind die Schritte des Spiels:
  1. Beginnen Sie bei Freund 1.
  2. Zählen Sie 2 Freunde im Uhrzeigersinn, das sind Freunde 1 und 2.
  3. Freund 2 verlässt den Kreis. Der nächste Start ist Freund 3.
  4. Zähle 2 Freunde im Uhrzeigersinn, das sind die Freunde 3 und 4.
  5. Freund 4 verlässt den Kreis. Der nächste Start ist Freund 5.
  6. Zähle 2 Freunde im Uhrzeigersinn, das sind die Freunde 5 und 1.
  7. Freund 1 verlässt den Kreis. Der nächste Start ist Freund 3.
  8. Zähle 2 Freunde im Uhrzeigersinn, das sind die Freunde 3 und 5.
  9. Freund 5 verlässt den Kreis. Nur Freund 3 ist übrig, also sind sie der Gewinner.

Beispiel 2:

• Eingabe: n = 6, k = 5
• Ausgabe: 1
• Erklärung:Die Freunde gehen in dieser Reihenfolge: 5, 4, 6, 2, 3. Der Gewinner ist Freund 1.

Einschränkungen:

• 1 <= k <= n <= 500

Nachverfolgung:

Könnten Sie dieses Problem in linearer Zeit mit konstantem Raum lösen?

Lösung:

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

Kontaktlinks

• LinkedIn
• GitHub

Das obige ist der detaillierte Inhalt vonFinden Sie den Gewinner des Kreisspiels. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!