배열 A가 있다고 가정합니다. 이것은 0과 1만 포함합니다. 여기서 K 비트 반전은 길이가 K인 (인접한) 하위 배열을 선택하고 동시에 하위 배열 n개의 비트를 반전시키는 것으로 구성됩니다. 배열에 0이 없도록 필요한 최소 K비트 플립 수를 찾아야 합니다. 그런 가능성이 없으면 -1을 반환합니다.
따라서 입력이 [0,0,0,1,0,1,1,0]이고 K =3과 같으면 첫 번째 시도에서 작업을 세 번 수행해야 하므로 출력은 3이 됩니다. A[0]을 A[3]으로 뒤집으면 배열은 [1,1,1,1,0,1,1,0]이 되고 두 번째 실행에서는 A[4]를 A[6]으로 뒤집습니다. [1,1,1,1,1,0,0,0]이고 세 번째 이동에서 A[5]를 A[7]로 변경하면 배열은 [1,1,1,1,1]이 됩니다. ,1,1,1].
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
n :=A의 크기
-
크기가 n인 배열 이동 정의
-
카운터 :=0
-
i:=0 초기화의 경우 i + K <=n일 때 업데이트(i를 1만큼 증가), −
-
i> 0이면 -
-
이동[i] :=이동[i] + 이동[i - 1]
-
-
((moves[i] mod 2) + A[i]) mod 2가 0이 아닌 경우 -
-
이동[i] :=이동[i] + 1
-
i + K
-
이동[i + K] - =1
-
-
(카운터 1 증가)
-
-
-
i
-
i> 0이면 -
-
이동[i] :=이동[i] + 이동[i - 1]
-
-
((moves[i] mod 2) + A[i]) mod 2가 0이 아닌 경우 -
-
반환 -1
-
-
-
반환 카운터
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
출력
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minKBitFlips(vector<int>& A, int K){
int n = A.size();
vector<int> moves(n);
int i;
int counter = 0;
for (i = 0; i + K <= n; i++) {
if (i > 0)
moves[i] += moves[i - 1];
if (!(((moves[i] % 2) + A[i]) % 2)) {
moves[i] += 1;
if (i + K < n)
moves[i + K] -= 1;
counter++;
}
}
for (; i < n; i++) {
if (i > 0)
moves[i] += moves[i - 1];
if (!(((moves[i] % 2) + A[i]) % 2))
return -1;
}
return counter;
}
};
main(){
Solution ob;
vector<int> v = {0,0,0,1,0,1,1,0};
cout << (ob.minKBitFlips(v, 3));
} 입력
{0,0,0,1,0,1,1,0}, 3 출력
3