이 튜토리얼에서는 배열에서 연속 1의 최대 수를 얻기 위해 뒤집어야 하는 0의 수를 찾을 것입니다.
우리는 문제를 해결하기 위해 슬라이딩 윈도우 접근 방식을 사용할 것입니다. 문제를 해결하는 단계를 살펴보겠습니다.
-
뒤집을 배열과 최대 0을 초기화합니다.
-
길이에 따라 창 시작, 끝 인덱스를 초기화합니다.
-
연속된 1의 길이와 시작 인덱스의 최대 하위 배열을 저장합니다.
-
끝 인덱스가 배열 길이와 교차할 때까지 배열을 반복합니다.
-
0 수가 최대 0 수보다 작으면 끝 인덱스를 증가시키고 현재 값이 0이면 0을 계산합니다.
-
0 개수가 최대 0 개수보다 크면 시작 인덱스를 증가시키고 현재 값이 0이면 0 개수를 줄입니다.
-
현재 창 길이가 이전 창 길이보다 큰 경우 최대 창을 업데이트합니다.
-
배열을 반복하고 창 시작 인덱스를 사용하여 0 인덱스를 인쇄합니다.
예시
코드를 봅시다.
#include <bits/stdc++.h>
using namespace std;
void zeroesIndexes(int arr[], int maxZeroes, int n) {
int start = 0, end = 0;
int zeroesCount = 0;
int bestWindowCount = 0, bestWindowStartIndex = 0;
while (end < n) {
if (zeroesCount <= maxZeroes) {
if (arr[end] == 0) {
zeroesCount++;
}
end++;
}
if (zeroesCount > maxZeroes) {
if (arr[start] == 0) {
zeroesCount--;
}
start++;
}
if ((end - start > bestWindowCount) && (zeroesCount <= maxZeroes)) {
bestWindowCount = end - start;
bestWindowStartIndex = start;
}
}
cout << "The indexes are ";
for (int i = 0; i < bestWindowCount; ++i) {
if(arr[bestWindowStartIndex + i] == 0)
cout << bestWindowStartIndex + i << " ";
}
}
int main() {
int arr[] = {1, 0, 0, 1, 1, 0, 1, 0, 1, 1};
int maxZeroes= 2;
zeroesIndexes(arr, maxZeroes, 10);
return 0;
} 출력
위의 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
The indexes are 5 7
결론
튜토리얼에서 질문이 있는 경우 댓글 섹션에 언급하세요.