N번째 이진 문자열에서 K번째 비트 찾기-PHP 튜토리얼-php.cn

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

DDD

풀어 주다： 2024-10-20 06:10:29

원래의

1041명이 탐색했습니다.

Find Kth Bit in Nth Binary String

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

힌트:

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

해결책:

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

접근하다:

재귀 문자열 구성:
- 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)) (변형된 부분)
주요 관찰:
- S_i의 길이는 2^i-1
- Sⁱ2i-1 >은 항상 "1"입니다.
- k가 전반에 속하면 Si-1에 속합니다.
- k가 정확히 중간 위치에 있다면 답은 "1"입니다.
- k가 후반이면 역반전된 부분에 해당합니다.
역전 및 반전:
- k를 전반부의 해당 위치에 매핑합니다. k' = 2i^{- k}
재귀 솔루션:
- n을 줄이고 k를 매핑하여 k번째 비트를 재귀적으로 결정합니다. 🎜> n = 1.까지

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_{번째 비트를 재귀적으로 찾습니다. >.}
- 가 mid보다 크면 역 반전된 후반부에서 해당 비트를 찾아서 뒤집습니다.
복잡성 분석:

시간 복잡도

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

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