가장 긴 연속 1 하위 문자열의 길이를 최대화하기 위해 제거해야 하는 0의 수를 최소화합니다.

이 기사에서는 C++ 문자열 연산과 관련된 흥미로운 문제를 살펴보겠습니다. 오늘 공부할 문제는 "1의 가장 긴 연속 부분 문자열의 길이를 최대화하기 위해 삭제해야 하는 0의 개수를 최소화"하는 방법입니다. 이 문제는 문자열 조작 및 동적 프로그래밍 기술을 연마할 수 있는 좋은 방법입니다.

문제 설명

이진 문자열이 주어지면 작업은 가장 긴 1 부분 문자열의 길이를 최대화하기 위해 제거해야 하는 0의 수를 최소화하는 것입니다.

C++ 솔루션

이 문제를 해결하기 위해 슬라이딩 윈도우 방식을 사용할 수 있습니다. 우리는 왼쪽 포인터와 오른쪽 포인터라는 두 개의 포인터를 유지할 것입니다. 처음에는 두 포인터가 모두 첫 번째 요소를 가리킵니다. 그런 다음 오른쪽 포인터를 오른쪽으로 계속 이동하겠습니다. '0'이 나타나면 카운터를 증가시킵니다. 카운터가 허용된 0 제거 횟수보다 커지면 '0'을 만날 때까지 왼쪽 포인터를 오른쪽으로 이동하고 카운터를 감소시킵니다.

또한 지금까지 본 1 하위 문자열의 최대 길이를 저장하기 위해 변수 maxLen을 유지 관리할 것입니다.

예

이 문제를 해결하는 C++ 코드입니다 -

으아악

출력

으아악

테스트 케이스 설명

이진 문자열 "110100110"을 사용하면 2개의 0을 제거할 수 있습니다.

이 문자열과 k 값을 maxSubstring 함수에 전달하면 왼쪽부터 스캔이 시작됩니다. '0'을 만날 때마다 zeroCount가 증가합니다. zeroCount가 k를 초과하면 '0'을 만나고 zeroCount가 감소할 때까지 왼쪽 포인터를 오른쪽으로 이동하기 시작합니다.

이 과정에서 최대 하위 문자열 길이인 1초인 maxLen을 지속적으로 업데이트합니다. 주어진 문자열에서 최대 2개의 0을 제거하지 않은 1s의 최대 하위 문자열 길이는 5입니다. 즉, 두 번째와 세 번째 '0'을 제거한 후 하위 문자열 "11111"입니다.

그래서 함수는 5를 반환합니다.

결론

이 질문은 슬라이딩 윈도우 기술을 효과적으로 사용하여 C++의 복잡한 문자열 조작 문제를 해결하는 방법을 보여줍니다. 이는 동적 프로그래밍과 문자열 처리 기술을 이해하고 연습하기 위한 훌륭한 질문입니다. C++ 코딩 기술을 향상하려면 이와 같은 질문을 계속 연습하세요.

위 내용은 가장 긴 연속 1 하위 문자열의 길이를 최대화하기 위해 제거해야 하는 0의 수를 최소화합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!