문자열에 연속적인 0 쌍이 없도록 뒤집기 횟수를 최소화하십시오.

여기서 연속된 0이 포함되지 않도록 이진 문자열을 조작해야 합니다. 연속된 0을 찾으면 0을 1로 변경해야 합니다. 따라서 총 0의 개수를 계산해야 합니다. 문자열에서 연속된 0을 모두 제거하려면 1로 변환해야 합니다.

문제 설명 − 0과 1만 포함하는 이진 문자열 'str'이 제공됩니다. 결과 문자열에 연속된 0이 포함되지 않도록 필요한 최소 뒤집기 횟수를 찾아야 합니다.

예제 예

으아아아 으아아아

설명

마지막 0에서 두 번째만 뒤집어야 합니다.

으아아아 으아아아

설명

연속되는 0쌍을 모두 제거하려면 2번째, 5번째, 7번째, 11번째 0을 뒤집어야 합니다.

으아아아 으아아아

설명

문자열에 연속된 0이 없으므로 뒤집을 필요가 없습니다.

방법 1

이 방법에서는 문자열을 처음부터 끝까지 반복하고 연속된 0이 포함된 경우 문자를 뒤집습니다. 마지막으로, 주어진 이진 문자열에서 연속된 0을 모두 제거하는 데 필요한 최소 뒤집기 횟수를 얻을 수 있습니다.

알고리즘

• 1단계 − 'cnt' 변수를 0으로 초기화하여 총 뒤집기 횟수를 저장합니다.

• 2단계 − 루프를 사용하여 이진 문자열을 반복합니다.

• 3단계 − 인덱스 'I'와 인덱스 'I +1'의 문자가 0이면 다음 문자를 뒤집고 'cnt' 변수의 값을 1만큼 늘립니다.

• 4단계 - for 루프의 반복이 완료되면 'cnt' 값을 반환합니다.

예

으아아아

출력

으아아아

시간 복잡도 − O(N), 이진 문자열을 반복합니다.

공간 복잡도 − O(1), 전체 개수를 저장하기 위해 일정한 공간을 사용하므로

결론

우리는 주어진 이진 문자열에서 연속적인 0 쌍을 제거하는 데 필요한 최소 뒤집기 횟수를 계산하는 방법을 배웠습니다. 사용자는 주어진 이진 문자열에서 연속적인 쌍을 제거하는 데 필요한 최소 뒤집기 횟수를 계산해 볼 수 있습니다.

위 내용은 문자열에 연속적인 0 쌍이 없도록 뒤집기 횟수를 최소화하십시오.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!