The title

portal

The text

Given an array A of zeros and ones, we can change up to K values from 0 to 1.

Returns the length of the longest (continuous) subarray containing only 1.

Example 1:

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

Output: 6 Explanation: [1,1,1,0,0,1,1,1,1,1] The bold digit is flipped from 0 to 1, and the longest subarray length is 6.

Example 2:

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

Output: 10:,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1 [0] bold digital flip from 0 to 1, the longest length of the subarray to 10.

Tip:

1 <= a. length <= 20000 0 <= K <= A.length A[I] is 0 or 1Copy the code

Source: LeetCode

The template

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

The problem solving

Analysis of the

One of the characteristics of array elements is that there are only two types of elements, 0 and 1, and there is a certain inclusive size of K for 0, so I think we can use the sliding window to solve this problem, and we want to return the length of the largest window traversed to the end. For the head pointer, we leave this the same, except that the miscellaneous pointer indicates that we count when 0 is detected. When the count reaches a certain length, we return the head pointer to the position where 0 was first detected so that the traversal continues until the end of the traversal

Initialize data

Right is no longer defined here but is defined within the loop

    int left = 0, lc = 0, rc = 0;// The corresponding left pointer, left count, right count
    int len = 0;// The final length returned by the program
Copy the code

Traversal cycle

The right pointer moves from 0 to asize-1

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

}
Copy the code

Counting rule

The right count counts the number of zeros traversed by the right pointer, so we can use 1-a [right] to determine if it is 0, and if it is, we add 1 to the count.

rc =rc + 1 - A[right];
Copy the code

Left counting same thing

lc =lc + 1 - A[left];
Copy the code

Then the problem comes. In the loop, the right pointer keeps moving backward, and if the left pointer does not move, it will not proceed. Analysis shows that only when the right pointer traverses k or more zeros will the left pointer move behind the first zero, and the movement of the left pointer also needs to be defined, so there are

 while (lc < rc - K) {
            lc =lc + 1 - A[left];
            ++left;
        }
Copy the code

Calculate the length of the

The length must be taken using fmax, and it needs to be updated in the loop, while the left side is constantly decreasing as it decreases, so it might as well go to the left side of the circular pointer movement, put it in the right side of the loop. The real length is the right pointer minus the left pointer plus 1. And then I’m going to take len and I’m going to take len.

len = fmax(len, right - left + 1);
Copy the code

Complete source code

int longestOnes(int* A, int ASize, int K) {
    int left = 0, lc = 0, rc = 0;
    int len = 0;
    for (int right = 0; right < ASize; ++right) {
        rc =rc + 1 - A[right];
        while (lc < rc - K) {
            lc =lc + 1 - A[left];
            ++left;
        }
        len = fmax(len, right - left + 1);
    }
    return len;
}

Copy the code

Running effect

Fortunately, it’s the same as the official solution