다음을 중국어로 번역하십시오. 0 부분 문자열 제거를 최소화하여 반복되는 이진 문자열에서 0의 모든 항목을 제거하십시오.

이 문제에서는 주어진 바이너리 문자열에서 0을 모두 제거해야 합니다. 동시에 연속된 0 쌍을 한 번에 제거하고 제거된 0 쌍의 총 개수를 계산해야 합니다.

주어진 문자열에서 연속되는 0의 쌍 수를 세어 문제를 해결할 수 있습니다. 이 튜토리얼에서는 문제를 해결하기 위한 두 가지 솔루션을 배우게 됩니다.

문제 설명 − 길이가 N인 원형 이진 문자열 str이 제공됩니다. 문자열에서 모든 0을 제거하는 데 필요한 연속된 0의 최소 개수를 찾아야 합니다.

예제 예

으아악 으아악

설명

str[0]과 str[1]을 함께 삭제할 수 있습니다. 그런 다음 str[4] 및 str[5]를 삭제할 수 있습니다. 따라서 연속된 0 쌍 2개를 제거해야 합니다.

으아악 으아악

설명

모든 0을 한 번에 제거할 수 있습니다.

으아악 으아악

설명

이진 문자열이 원형이므로 str[0], str[1] 및 str[7]을 함께 제거합니다. 다음으로 str[5]와 str[6]을 함께 제거할 수 있습니다.

접근법 1

이 방법에서는 주어진 문자열에서 연속된 0 쌍의 총 개수를 찾아 주어진 질문에 답할 것입니다.

알고리즘

• 1단계 - 'cnt' 변수를 0으로 초기화합니다.

• 2단계 - 'isOne' 변수를 false 값으로 초기화하여 주어진 문자열에서 숫자 1을 추적합니다.

• 3단계 - 루프를 사용하여 문자열을 반복합니다. 루프에서 현재 문자가 '0'이면 'cnt' 값을 1만큼 늘립니다.

• 4단계 − while 루프를 사용하여 '0'인 다음 문자를 계속 찾고 'I' 값을 1만큼 늘릴 때까지 반복합니다.

• 5단계 - 현재 문자가 '1'인 경우 'isOne' 변수의 값을 true로 변경하여 문자열에 '1'이 하나 이상 포함되어 있음을 나타냅니다.

• 6단계 − 루프 반복이 완료되면 'isOne' 값이 false인 경우 문자열에 0만 포함된다는 의미입니다.

• 7단계 − 첫 번째와 마지막 문자가 '0'인 경우 문자열이 원형이므로 'cnt' 값을 1만큼 줄입니다.

• 8단계 − 'cnt' 값을 반환합니다.

Example

의 중국어 번역은 다음과 같습니다:

Example

으아악

출력

으아악

공간 복잡성 - O(1)

방법 2

이 방법에서는 인접한 요소의 차이를 계산하여 모든 0을 제거하는 데 필요한 0 제거 하위 문자열의 최소 개수를 계산합니다.

알고리즘

• 1단계 − 'cnt' 및 'isOne' 변수를 정의하고 각각 0과 false로 초기화합니다.

• 2단계 − for 루프를 사용하여 N-1 반복을 만듭니다. 여기서 N은 문자열 길이입니다.

• 3단계 − 루프에서 현재 문자가 '0'이고 다음 문자가 '1'인지 확인하고 'cnt' 값을 1만큼 늘립니다. 그렇지 않으면 'isOne' 값을 변경합니다. 변수를 true로 설정합니다.

• 4단계 - 마지막 문자가 '0'이고 첫 번째 문자가 '1'이면 'cnt' 값을 1만큼 늘립니다.

• 5단계 - 'isOne' 값이 false인 경우 1을 반환합니다.

• 6단계 - 'cnt' 변수의 값을 반환합니다.

Example

의 중국어 번역은 다음과 같습니다:

Example

으아악

출력

으아악

결론

우리는 주어진 문제를 해결하기 위한 두 가지 다른 솔루션을 살펴보았습니다. 첫 번째 방법에서는 연속된 0 쌍의 총 개수를 계산하고, 두 번째 방법에서는 일치하지 않는 인접 문자의 총 개수를 계산합니다.

위 내용은 다음을 중국어로 번역하십시오. 0 부분 문자열 제거를 최소화하여 반복되는 이진 문자열에서 0의 모든 항목을 제거하십시오.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!