Cari Pemenang Permainan Pekeliling

1823. Cari Pemenang Permainan Pekeliling

Sederhana

Terdapat n rakan sedang bermain permainan. Rakan-rakan duduk dalam bulatan dan dinomborkan dari 1 hingga n dalam urutan mengikut arah jam. Secara lebih formal, bergerak mengikut arah jam daripada rakan i^th membawa anda ke (i+1)^th rakan untuk 1 <= i < n, dan bergerak mengikut arah jam daripada n^th rakan membawa anda ke 1^st rakan.

Peraturan permainan adalah seperti berikut:

1. Mula pada 1^st kawan.
2. Kira k rakan seterusnya mengikut arah jam termasuk rakan yang anda mulakan. Pengiraan melingkari bulatan dan mungkin mengira beberapa rakan lebih daripada sekali.
3. Rakan terakhir yang anda kira meninggalkan bulatan dan kalah dalam permainan.
4. Jika masih terdapat lebih daripada seorang rakan dalam bulatan, kembali ke langkah 2 bermula daripada rakan sejurus mengikut arah jam rakan yang baru kalah dan mengulangi.
5. Jika tidak, rakan terakhir dalam bulatan memenangi permainan.

Memandangkan bilangan rakan, n, dan integer k, kembalikan pemenang permainan.

Contoh 1:

• Input: n = 5, k = 2
• Output: 3
• Penjelasan: Berikut ialah langkah-langkah permainan:
  1. Mulakan pada rakan 1.
  2. Kira 2 rakan mengikut arah jam, iaitu rakan 1 dan 2.
  3. Rakan 2 meninggalkan kalangan. Permulaan seterusnya ialah kawan 3.
  4. Kira 2 rakan mengikut arah jam, iaitu rakan 3 dan 4.
  5. Rakan 4 meninggalkan kalangan. Permulaan seterusnya ialah rakan 5.
  6. Kira 2 rakan mengikut arah jam, iaitu rakan 5 dan 1.
  7. Rakan 1 meninggalkan kalangan. Permulaan seterusnya ialah kawan 3.
  8. Kira 2 rakan mengikut arah jam, iaitu rakan 3 dan 5.
  9. Rakan 5 meninggalkan kalangan. Hanya kawan 3 sahaja lagi, jadi merekalah pemenangnya.

Contoh 2:

• Input: n = 6, k = 5
• Output: 1
• Penjelasan: Rakan-rakan keluar mengikut urutan ini: 5, 4, 6, 2, 3. Pemenang ialah kawan 1.

Kekangan:

• 1 <= k <= n <= 500

Susulan:

Bolehkah anda menyelesaikan masalah ini dalam masa linear dengan ruang malar?

Penyelesaian:

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

Pautan Kenalan

• LinkedIn
• GitHub

Atas ialah kandungan terperinci Cari Pemenang Permainan Pekeliling. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!