N번째 이진 문자열에서 K번째 비트 찾기

1545. N번째 이진 문자열에서 K번째 비트 찾기

난이도:중

주제: 문자열, 재귀, 시뮬레이션

두 개의 양의 정수 n과 k가 주어지면 이진 문자열 S_n은 다음과 같이 구성됩니다.

• S₁ = "0"
• S_i = S_{i - 1} "1" reverse(invert(S_{i - 1})) for i > 1

연결 연산을 나타내는 곳에서 reverse(x)는 반전된 문자열 x를 반환하고 invert(x)는 x의 모든 비트를 반전합니다(0은 1로 변경되고 1은 0으로 변경).

예를 들어 위 시퀀스의 처음 4개 문자열은 다음과 같습니다.

• S₁ = "0"
• S₂ = "011"
• S₃ = "0111001"
• S₄ = "011100110110001"

Sn의 _k번째 비트를 반환합니다. 주어진 n에 대해 k가 유효하다는 것이 보장됩니다.

예 1:

• 입력: n = 3, k = 1
• 출력: "0"
• 설명: S₃은 "0111001"입니다. 첫 번째^번째 비트는 "0"입니다.

예 2:

• 입력: n = 4, k = 11
• 출력: "1"
• 설명: S₄는 "011100110110001"입니다. 11^번째 비트는 "1"입니다.

예 3:

• 입력: n = 3, k = 2
• 출력: "0"

제약조건:

• 1
• 1 n - 1

힌트:

1. n이 작으므로 S1에서 Sn까지 구성하는 과정을 간단하게 시뮬레이션할 수 있습니다.

해결책:

각 이진 문자열 S_n을 생성하는 데 사용되는 재귀 프로세스를 이해하고 이를 사용하여 전체 문자열을 구성하지 않고 k번째 비트를 결정해야 합니다. 문자열입니다.

접근하다:

1. 재귀 문자열 구성:

   • S₁ = "0".
   • 나를 위해 > 1:
     • S_i는 다음과 같이 구성됩니다. S_i = S_i-1 "1" reverse(invert(S_i-1))
   • 즉, S_i는 세 부분으로 구성됩니다.
     • S_i-1(원작편)
     • "1"(가운데 비트)
     • reverse(invert(S_i-1)) (변형된 부분)

2. 주요 관찰:

   • S_i의 길이는 2^i-1
   입니다.
   • Sⁱ2i-1 >은 항상 "1"입니다.
   • k가 전반에 속하면 Si-1에 속합니다.
   • k가 정확히 중간 위치에 있다면 답은 "1"입니다.
   • k가 후반이면 역반전된 부분에 해당합니다.

3. 역전 및 반전:

   후반부의 비트를 결정하려면 다음을 사용하여
   • k를 전반부의 해당 위치에 매핑합니다. k' = 2i ^{- k}
   원래 절반에서 이 위치의 비트가 반전되었으므로 결과를 뒤집어야 합니다.

4. 재귀 솔루션:

   • n을 줄이고 k를 매핑하여 k번째 비트를 재귀적으로 결정합니다. 🎜> n = 1.까지
이 솔루션을 PHP로 구현해 보겠습니다:

1545. N번째 이진 문자열에서 K번째 비트 찾기

설명:

<?php
/**
 * @param Integer $n
 * @param Integer $k
 * @return String
 */
function findKthBit($n, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}
?>

기본 사례
• : n = 1인 경우 Si는 "0"입니다. 이므로 k에 대해 가능한 유일한 값은 "0"입니다.
재귀 단계
• : 중간 지수
  • mid를 계산합니다. 이는 2n-1입니다.
  • k가 중간 인덱스와 일치하면 "1"을 반환합니다.
  • k가 mid보다 작으면 k번째 비트는 전반부에 있으므로 Sn-1k_{번째 비트를 재귀적으로 찾습니다. >.}
  k
  • 가 mid보다 크면 역 반전된 후반부에서 해당 비트를 찾아서 뒤집습니다.
  복잡성 분석:

시간 복잡도

:
• O(n) 왜냐하면 각 재귀 호출은 n을 1씩 감소시키기 때문입니다. 공간 복잡도
: 재귀 호출 스택의 경우
• O(n) 예제 연습:

입력
1. :

   n = 3 , k = 1

   • S₃ = "0111001"
   • k = 1이 전반부에 속하므로 Sk = 1을 찾습니다. >2.
   • S2 = "011" , k = 1 "0"에 해당합니다.

2. 입력: n = 4 , k = 11

   • S4 = "011100110110001"
   • S4의 중간 지수는 8입니다.
   • k = 11은 후반에 해당합니다.
   • k = 11을 전반부의 해당 비트에 매핑: k' = 2 4 ^{- 11 = 5}.
   • S3에서 "0"인 _{k = 5}을 찾아 뒤집습니다. "1"로.

이 솔루션은 문자열 구성의 재귀 및 속성을 활용하여 전체 문자열 생성을 방지하므로 더 큰

n에도 효율적입니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서

저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.

• 링크드인
• 깃허브

위 내용은 N번째 이진 문자열에서 K번째 비트 찾기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!