바이너리 문자열을 아름답게 만들기 위한 최소 변경 횟수

2914. 바이너리 문자열을 아름답게 만들기 위한 최소 변경 횟수

난이도:중

주제: 문자열

짝수 길이의 인덱스가 0인 바이너리 문자열 s가 제공됩니다.

다음과 같이 하나 이상의 하위 문자열로 분할할 수 있는 경우 문자열은 아름답다.

• 각 하위 문자열에는 짝수 길이가 있습니다.
• 각 하위 문자열에는 1만 1 또는 0만 포함됩니다.

s 안의 문자를 0이나 1로 변경할 수 있습니다.

문자열을 아름답게 만드는 데 필요한 최소 변경 횟수를 반환합니다.

예 1:

• 입력: s = "1001"
• 출력: 2
• 설명: s[1]을 1로, s[3]을 0으로 변경하여 문자열 "1100"을 얻습니다.
  • 문자열 "1100"은 "11|00"으로 분할할 수 있기 때문에 아름답다는 것을 알 수 있습니다.
  • 문자열을 아름답게 만드는 데 필요한 최소 변경 횟수는 2라는 것이 증명될 수 있습니다.

예 2:

• 입력: s = "10"
• 출력: 1
• 설명: s[1]을 1로 변경하여 문자열 "11"을 얻습니다.
  • 문자열 "11"은 "11"로 분할할 수 있기 때문에 아름답다는 것을 알 수 있습니다.
  • 문자열을 아름답게 만드는 데 필요한 최소 변경 횟수는 1임을 증명할 수 있습니다.

예 3:

• 입력: s = "0000"
• 출력: 0
• 설명: 문자열 "0000"이 이미 아름답기 때문에 변경할 필요가 없습니다.

제약조건:

• 2 5
• s의 길이는 짝수입니다.
• s[i]는 '0' 또는 '1'입니다.

힌트:

1. 유효한 파티션의 경우 각 부분은 동일한 문자의 짝수로 구성되므로 각 부분을 정확히 2의 길이로 추가로 분할할 수 있습니다.
2. 첫 번째 힌트를 확인한 후 전체 문자열을 크기 2의 분리된 블록으로 분해하고 해당 블록을 아름답게 만드는 데 필요한 최소 변경 횟수를 찾을 수 있습니다.

해결책:

이진 문자열 s의 모든 문자 쌍이 "00" 또는 "11"인지 확인해야 합니다. 쌍이 이 두 패턴 중 하나에 속하지 않는 경우 일치하도록 문자 중 하나를 변경해야 합니다.

단계별 해결 방법은 다음과 같습니다.

1. 문자열을 블록으로 나누기: 길이가 2인 블록으로 아름다운 문자열을 만들 수 있으므로 문자열을 2단계로 반복할 수 있습니다.

2. 개수 변경: 2자로 구성된 각 블록에 대해 주요 문자(0 또는 1)를 결정해야 합니다. 다수 문자와 일치하도록 블록의 소수 문자를 변경하겠습니다.

3. 최소 변경 사항 계산: 각 블록에 대해 두 문자가 모두 다른 경우 1번 변경이 필요합니다. 동일하다면 변경할 필요가 없습니다.

이 솔루션을 PHP로 구현해 보겠습니다: 2914. 바이너리 문자열을 아름답게 만들기 위한 최소 변경 횟수

<?php
/**
 * @param String $s
 * @return Integer
 */
function minChanges($s) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage
echo minChanges("1001"); // Output: 2
echo minChanges("10");   // Output: 1
echo minChanges("0000"); // Output: 0
?>

설명:

1. 함수 정의: 이진 문자열 s를 사용하는 minChanges 함수를 정의합니다.

2. 초기화: 필요한 변경 횟수를 추적하기 위해 $changes 변수를 초기화합니다.

3. 문자열 반복: 문자열을 반복하면서 두 문자의 각 블록을 확인하기 위해 매번 2씩 증가합니다.

   • $first는 현재 위치의 문자입니다.
   • $second는 다음 위치의 문자입니다.

4. 변경 사항 확인: 현재 블록의 문자가 다른 경우 $changes 카운터를 1씩 증가시킵니다.

5. 반환 결과: 마지막으로 필요한 총 변경 횟수를 반환합니다.

복잡성:

• 시간 복잡도: O(n), 여기서 n은 문자열의 길이입니다. 문자열을 한 번 반복합니다.
• 공간 복잡도: O(1), 일정한 양의 추가 공간을 사용하고 있기 때문입니다.

이 솔루션은 O(n) 시간 복잡도에서 작동합니다. 여기서 n은 문자열의 길이이므로 주어진 제약 조건에 효율적입니다.

연락처 링크

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

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

• 링크드인
• 깃허브

위 내용은 바이너리 문자열을 아름답게 만들기 위한 최소 변경 횟수의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!