The title

portal

The text

In array A, which contains only zeros and ones, A k-bit flip involves selecting A (continuous) subarray of length K, simultaneously changing each 0 in the subarray to A 1, and each 1 to A 0.

Returns the minimum number of k-bit flips required so that the array has no element with a value of 0. If that is not possible, return -1.

Example 1:

Input: A = [0,1,0], K = 1

Output: 2 Explanation: First flip A[0], then flip A[2].

Example 2:

Input: A = [1,1,0], K = 2

Explanation: No matter how we flip a subarray of size 2, we can’t make the array [1,1,1].

Example 3:

Input: A = [0,0,0,1, 1,1,0], K = 3

Output: 3: flip A [0], A [1], A [2] : A turn into,1,1,1,0,1,1,0 [1] A [4], A [5], A [6] : A turn into,1,1,1,1,0,0,0 [1] A [5], A [6], A [7] : Become A,1,1,1,1,1,1,1 [1]

Tip:

1 <= A.length <= 30000
1 <= K <= A.length
Copy the code

Source: LeetCode

The template

int minKBitFlips(int* A, int ASize, int K){}Copy the code

The problem solving

Analysis of the

For a given array of 01, flip K subarrays (0->1,1->0) to find the minimum number of times that all elements are 1. If this cannot be done, return -1. This problem applies many methods: greedy algorithm, difference, sliding window.

Greedy algorithms:

What we want to flip over is a small window of length K, which can be flipped over, and if you flip it twice, it doesn’t flip over.

Sliding window:

Determine whether every element needs to be flipped from there.

Difference array:

If flips are needed, the number of flips is recorded. The record is the first (I) plus and the last (I +k) minus of the difference traversal. Finally, use difference to calculate the cumulative number of flipping; If you need to flip, but there are less than K remaining elements, then you cannot achieve the goal of setting all elements to 1, and return -1.

coding

Define and initialize

Here is the definition of the creation and initialization of the difference array, as well as the final number of reversals that need to be returned ans, which for revCnt counts as the first diff[I] of our difference array;

int diff[ASize + 1];
    memset(diff, 0.sizeof(diff));
    int ans = 0, revCnt = 0;
Copy the code

Establish traverse

for (int i = 0; i < ASize; ++i) {

}
Copy the code

RevCnt is bound to diff[I]

revCnt += diff[i];
Copy the code

To determine whether it needs to be flipped and the subsequent length

if ((A[i] + revCnt) % 2= =0) {
            if (i + K > ASize) {
                return - 1; }}Copy the code

If the flip performs the operation

++ans;
++revCnt;
--diff[i + K];
Copy the code

The complete code

int minKBitFlips(int* A, int ASize, int K) {
    int diff[ASize + 1];
    memset(diff, 0.sizeof(diff));
    int ans = 0, revCnt = 0;
    for (int i = 0; i < ASize; ++i) {
        revCnt += diff[i];
        if ((A[i] + revCnt) % 2= =0) {
            if (i + K > ASize) {
                return - 1; } ++ans; ++revCnt; --diff[i + K]; }}return ans;
}

Copy the code

For example, the process