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