문자열을 0의 문자열과 1의 문자열로 구성하기 위한 최소 제거 횟수

"0개 하위 문자열의 문자열 연결을 위한 최소 삭제"라는 질문에는 문자열 조작에 대한 작업이 포함됩니다. 입력으로 0과 1의 문자열이 주어지면 결과는 연속 0의 하위 문자열을 생성하기 위해 제거해야 하는 최소 0 수를 반영하는 정수입니다.

즉, 문제는 다음과 같이 공식화될 수 있습니다. 0과 1로 구성된 문자열이 주어지면 나머지 문자열에 연속적인 0 기간이 포함되도록 하려면 몇 개의 0을 제거해야 할까요?

알고리즘

1단계: 변수 초기화

• 현재 0 시퀀스의 길이를 기록하는 카운트 변수를 정의합니다.

• 지금까지 발생한 가장 긴 0 시퀀스를 추적하려면 max_count 변수를 정의하세요.

• 두 변수를 모두 0으로 설정하세요.

2단계: 문자열 탐색

루프를 사용하여 문자열의 각 문자를 반복합니다.

3단계: 제로 감지

현재 문자가 0이면 count 변수를 증가시킵니다.

4단계: 1회 테스트

• 현재 문자가 1이면 count 변수와 max_count 변수를 비교합니다.

• count 변수가 max_count 변수보다 큰 경우 max_count 변수를 count 변수와 동일하게 설정하세요.

• count 변수를 0으로 재설정하세요.

5단계: 루프 완료

문자열의 모든 문자가 처리될 때까지 이 과정을 반복하세요.

6단계: 최소 삭제 계산

나머지 0이 0으로 분리되지 않도록 모든 0을 제거하는 데 필요한 최소 삭제 횟수는 문자열 길이에서 max_count를 빼서 계산할 수 있습니다.

7단계: 결과 출력

결과를 콘솔에 인쇄하세요.

따라야 할 방법

• 동적 방법

• 반복 방법

방법 1: 동적 방법

동적 프로그래밍을 사용하면 이 문제를 효율적으로 해결할 수 있습니다. 연속적인 0의 하위 문자열을 생성하려면 배열 dp[]를 생성할 수 있습니다. 여기서 dp[i]는 하위 문자열 s[0...i]에서 제거해야 하는 최소 0 수를 나타냅니다. 빈 부분 문자열에서 제거해야 할 최소 0 개수는 0이므로 dp[0]을 0으로 초기화할 수 있습니다.

그런 다음 문자열 s를 반복하고 dp[i]를 −

로 업데이트할 수 있습니다.

• s[i]가 "0"이면 dp[i] = dp[i-1]입니다. 연속된 0의 하위 문자열에 s[i]를 포함하거나 제거할 수 있기 때문입니다.

• s[i]가 "1"이면 연속된 0의 하위 문자열을 포함하는 i에 가장 가까운 인덱스 j를 가져와야 합니다. 이는 i-1에서 0까지 반복하고 하위 문자열 s[j...i]에 연속적인 0이 포함되어 있는지 확인하여 수행할 수 있습니다. 인덱스 j가 발견되면 dp[i] = dp[j-1] + (i-j+1)입니다. 여기서 dp[j-1]은 하위 문자열 s[에서 제거해야 하는 최소 0 수를 나타냅니다. .j-1] 및 (i-j+1)은 연속된 0의 하위 문자열 s[j...i]를 얻기 위해 제거해야 하는 1의 총 개수입니다. 그러한 인덱스 j가 발견되지 않으면 연속된 0의 하위 문자열에 s[i]를 포함할 수 없으므로 dp[i] = dp[i-1]입니다.

  마지막으로 연속된 0의 부분 문자열을 얻기 위해 전체 문자열 s에서 제거해야 하는 최소 0 개수는 dp[n-1]로 지정됩니다. 여기서 n은 문자열 s의 길이입니다.

예 1

다음 프로그램은 위에서 논의한 방법을 사용하여 먼저 표준 입력에서 입력 문자열을 읽은 다음 0의 모든 하위 문자열을 식별합니다. 그런 다음 가장 긴 0 부분 문자열의 길이와 각 0 부분 문자열을 연결하여 생성된 문자열의 길이를 계산합니다. 필요한 최소 제거 수를 결정하기 위해 궁극적으로 모든 0 하위 문자열의 합계에서 가장 긴 0 하위 문자열의 길이를 빼고 그 결과를 표준 출력에 표시합니다.

으아악

출력

으아악

방법 2: 반복 방법

이 방법은 두 변수 count와 max_count의 값을 업데이트하면서 주어진 문자열을 문자별로 반복하는 간단한 반복 방법을 사용합니다. 이 메서드는 현재 문자가 0인지 1인지에 따라 count 및 max_count 변수의 값을 업데이트합니다. 그런 다음 max_count와 가장 긴 0 하위 문자열 길이 간의 차이를 제공합니다.

예 2

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

예 2

이 코드는 나머지가 0으로 구분되지 않도록 이진 문자열에서 모든 0을 제거하는 데 필요한 최소 제거 횟수를 계산하는 C++ 소프트웨어입니다. min_deletions 함수는 이진 문자열을 입력으로 사용하고 루프를 사용하여 문자열의 각 문자를 반복합니다. 루프는 0을 만날 때마다 count 변수를 증가시키고 1을 만나면 0으로 재설정합니다. count 변수의 최대값은 max_count에 저장되며, 마지막으로 max_count에서 문자열의 길이를 빼서 필요한 최소 삭제 횟수를 구합니다. 그러면 결과가 사용자에게 표시됩니다.

으아악

출력

으아악

결론

0의 모든 부분 문자열을 결정하고, 0의 각 부분 문자열을 연결하여 생성된 문자열의 길이를 계산하고, 0의 가장 긴 부분 문자열의 길이를 결정하는 것이 주어진 문제를 해결하기 위한 세 단계입니다. 그러면 가장 큰 0 부분 문자열의 길이를 모든 0 부분 문자열의 합에서 빼서 필요한 최소 삭제 횟수를 얻을 수 있습니다.

답을 얻기 위해 사용하는 방법은 간단하고 효율적이며 선형 시간으로 실행되므로 대규모 입력에 적합합니다. 그러나 동적 프로그래밍과 같은 보다 정교한 방법을 적용하면 더욱 향상될 수 있습니다.

위 내용은 문자열을 0의 문자열과 1의 문자열로 구성하기 위한 최소 제거 횟수의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!