순환 게임의 승자를 찾아보세요

1823. 순환게임의 승자를 찾아보세요

중간

게임을 하고 있는 친구가 n명 있습니다. 친구들은 원 안에 앉아 시계방향으로 1부터 n까지 번호가 매겨져 있습니다. 더 공식적으로 말하면, i^번째 친구부터 시계 방향으로 이동하면 1 ^번째 친구가 1 <= i < n, n^번째 친구부터 시계방향으로 이동하면 첫 번째^번째 친구

가 나옵니다.

게임의 규칙은 다음과 같습니다.

1. 시작첫^첫친구
2. 시작한 친구를 포함하여 시계 방향으로 다음 k명의 친구를 셉니다. 계산은 원을 중심으로 진행되며 일부 친구의 수는 두 번 이상 계산될 수 있습니다.
3. 마지막에 세었던 친구가 서클을 떠나 게임에서 패배합니다.
4. 아직 서클에 친구가 2명 이상 있으면, 방금 진 친구의 시계방향부터 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
    }
}

연락처 링크

• 링크드인
• 깃허브

위 내용은 순환 게임의 승자를 찾아보세요의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!