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 ith membawa anda ke (i+1)th rakan untuk 1 <= i < n, dan bergerak mengikut arah jam daripada nth rakan membawa anda ke 1st rakan.
Peraturan permainan adalah seperti berikut:
-
Mula pada 1st kawan.
- Kira k rakan seterusnya mengikut arah jam termasuk rakan yang anda mulakan. Pengiraan melingkari bulatan dan mungkin mengira beberapa rakan lebih daripada sekali.
- Rakan terakhir yang anda kira meninggalkan bulatan dan kalah dalam permainan.
- 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.
- 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:
- Mulakan pada rakan 1.
- Kira 2 rakan mengikut arah jam, iaitu rakan 1 dan 2.
- Rakan 2 meninggalkan kalangan. Permulaan seterusnya ialah kawan 3.
- Kira 2 rakan mengikut arah jam, iaitu rakan 3 dan 4.
- Rakan 4 meninggalkan kalangan. Permulaan seterusnya ialah rakan 5.
- Kira 2 rakan mengikut arah jam, iaitu rakan 5 dan 1.
- Rakan 1 meninggalkan kalangan. Permulaan seterusnya ialah kawan 3.
- Kira 2 rakan mengikut arah jam, iaitu rakan 3 dan 5.
- 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:
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
}
}
Salin selepas log masuk
Pautan Kenalan
Atas ialah kandungan terperinci Cari Pemenang Permainan Pekeliling. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!