485
Title Description
Train of thought sliding window
In fact, this problem doesn't need sliding window. If you encounter 1, CNT + + and 0cnt, it's OK to clear. But dedicated job hunting dogs must practice sliding window
class Solution {
public:
int findMaxConsecutiveOnes(vector<int>& nums) {
int l = 0, r = 0;
int len = nums.size();
int ans = 0;
while(r < len) {
if(nums[r] == 1) {
r++;
} else {
//r will encounter 0 first and l will stop at the first 1
//At this time, r-l is the length of 1
ans = max(ans, r - l);
r++;
l = r;
}
}
//eg: [0,1,1] [1,1,1] when the last window arrives, r exceeds the length of the array, so it needs to be calculated again
ans = max(ans, r - l);
return ans;
}
};
The idea of the above code sliding:
If you encounter a 1, r + +, expand the window and do not perform other operations; This leads to the fact that if the ending is 1, it must be counted again
If you encounter a 0, calculate the result. Since it is delayed here, r = 0, indicating that the [l, R) interval is a correct interval, and then R + +, L = R, cross this 0. Generally, when you encounter R-L, you have to calculate it again at last
Time O(n)
Space O(1)
It's quite natural to do this question, but it's strange to do the next one
1004
Title Description
Train of thought sliding window
This problem cannot directly judge 0 with a single pointer and then clear it, because each 0 can be used as a starting point.
Then use the sliding window,
class Solution {
public:
int longestOnes(vector<int>& A, int K) {
int len = A.size();
if(K == len) return len;
int left = 0, right = 0;
int ans = 0;
int zeroSum = 0;
while(right < len) {
if(A[right] == 0) {
zeroSum++;
}
while(zeroSum > K) {
if(A[left] == 0) {
zeroSum--;
}
left++;
}
ans = max(ans, right - left + 1);
right++;
}
return ans;
}
};
The idea is also obvious
When you encounter a 0, first turn it into a 1. If the number of times is enough, it's OK;
However, if it is found to be multi-purpose, you need to constantly narrow the left boundary until a 0 is discarded
Then calculate the interval size every time.
Ah, when you think about it like this, you will wonder why the first question needs to be calculated again in the end. Is the idea not good enough? Can you use the insect movement method as the second question?
ps: insect movement method
The right boundary keeps creeping. It is found that the left boundary keeps creeping in special periods. It is correct every time it stops.
So we began to process the code of the first question.
This is the first version
class Solution {
public:
int findMaxConsecutiveOnes(vector<int>& nums) {
int l = 0, r = 0;
int len = nums.size();
int ans = 0;
while(r < len) {
if(nums[r] == 0)
{
l = r;
while(nums[r] == 0) {
l++;
r++;
}
}
ans = max(ans, r - l + 1);
r++;
}
//eg: [0,1,1] [1,1,1] when the last window arrives, r exceeds the length of the array, so it needs to be calculated again
return ans;
}
};
The idea is to expand the window when encountering 1
When 0 is encountered, find an interval with a starting point other than 0
Then calculate the window size each time
It's strange to look at it, otherwise
Case [0] is out of bounds because r in while is out of bounds
Then he changed it again
class Solution {
public:
int findMaxConsecutiveOnes(vector<int>& nums) {
int l = 0, r = 0;
int len = nums.size();
int ans = 0;
while(r < len) {
if(nums[r] == 0)
{
l = r;
while(r < len && nums[r] == 0) {
l++;
r++;
}
} else {
ans = max(ans, r - l + 1);
r++;
}
}
return ans;
}
};
Conditions are added to judge whether r has reached the boundary in while
This alone is not enough. If case [0], ans will be equal to 1 for the first time, which is also wrong
So put the following code into else, that is, the window size is calculated only when num [R] is equal to 1.
That's right
However, 1004 code does not have [0], and 0 will be wrong. The reason is that its L will become 1, and then the calculation result is 0 - 1 + 1 = 0,
Obviously, k=0 of 1004 is 485, so we change the code again
class Solution {
public:
int findMaxConsecutiveOnes(vector<int>& nums) {
int l = 0, r = 0;
int len = nums.size();
int ans = 0;
int zeroSum= 0;
while(r < len) {
if(nums[r] == 0) {
zeroSum++;
}
while(zeroSum > 0) {
if(nums[l] == 0) {
zeroSum--;
}
l++;
}
ans = max(ans, r - l + 1);
r++;
}
//eg: [0,1,1] [1,1,1] when the last window arrives, r exceeds the length of the array, so it needs to be calculated again
return ans;
}
};
Simplification
class Solution {
public:
int findMaxConsecutiveOnes(vector<int>& nums) {
int l = 0, r = 0;
int len = nums.size();
int ans = 0;
int zeroSum= 0;
while(r < len) {
if(nums[r] == 0) {
while(nums[l] != 0) {
l++;
}
l++;
}
ans = max(ans, r - l + 1);
r++;
}
return ans;
}
};
Changed for a long time... I went to play the empty knight on the way. Of course, I found that the empty knight was more autistic, and then came back.
The difficulty is that L + + must be used at the end of the while loop;
Because we l need to stay in the first 1 position. I didn't find out at first
while(zeroSum > K) {
if(A[left] == 0) {
zeroSum--;
}
left++;
}
This code finds the place where A[left] is 1 again.
After saying so much, the main thing is to express the seemingly same topics. You can draw inferences from one example, but don't think about mechanically copying. Sometimes a careless person will make a mess.