58同城承德网站建设,关于做香奈儿网站的PPT,免费建设论坛网站,如何设计企业网站一.题目描述
最大连续1的个数 这道题要我们找最大连续1的个数#xff0c;看到“连续”二字#xff0c;我们要想到滑动窗口的方法。滑动窗口的研究对象是一个连续的区间#xff0c;这个区间需要满足某个条件。那么本题要找的是怎样的区间呢#xff1f;是一个通过翻转0后得到…一.题目描述
最大连续1的个数 这道题要我们找最大连续1的个数看到“连续”二字我们要想到滑动窗口的方法。滑动窗口的研究对象是一个连续的区间这个区间需要满足某个条件。那么本题要找的是怎样的区间呢是一个通过翻转0后得到连续1的区间而最多可以翻转k个字符。
故要找的是包含0的个数不超过k的区间因为如果超过k个0即使经过翻转该区间的1也还是不连续。
题意转化过来后本题便不再困难。
二.思路分析
滑动窗口是在暴力解法的基础上优化过来的。本题的暴力解法就是两层for循环枚举所有的区间找出满足条件的区间通过比较得到最长的区间长度结果就是数组中连续1的最大个数。
class Solution {
public:int longestOnes(vectorint nums, int k) {int n nums.size();int ret 0;for (int left 0; left n; left){int zero 0;//记录0的个数for (int right left; right n; right){if (nums[right] 0){zero;}//如果0的个数已经超过k,right向后枚举的区间肯定也不符合要求if (zero k){break;}ret max(ret, right - left 1);}}return ret;}
};
要想用滑动窗口首先要证明right没有回退的必要 如图right从left位置出发依次向后枚举到图中的位置[left, right]区间内0的个数大于k,停了下来。这说明[left, right - 1]区间是满足要求的。 按照暴力枚举策略left向右移动一步right回退到left位置。但最终right还是会回到原来的标记处。因为通过上一轮枚举我们可知图中大括号标记的区间都是符合条件的而right只有在区间不满足要求时才会停下。所以right没有必要回退留在原地即可。 那么此时[left, right]区间是否符合条件呢答案是不一定。因为可能left跳过的是一个1, 0的数量并没有减少也有可能跳过了一个0区间内刚好有k个0。 当区间符合条件时我们让right继续向后移动接下来的步骤就和上面一样了。当区间不符合条件时right向后枚举的区间就更不满足了所以我们让left继续向右移动直到区间满足要求为止。 故判断应该是一个循环语句不能简单地只判断一次。 三.代码编写 按照滑动窗口的模版找到各个条件即可。当枚举的情况满足要求时应该更新结果。什么时候满足要求呢
1.进窗口之后zerok,符合要求
2.进窗口之后zerok,经过若干次出窗口操作后zerok 满足要求
故更新结果应放在整个循环的最后面
class Solution {
public:int longestOnes(vectorint nums, int k) {int n nums.size();int zero 0;//记录窗口内0的个数int left 0, right 0;int ret 0;while (right n){//进窗口if (nums[right] 0){zero;}//判断while (zero k){//出窗口if (nums[left] 0){zero--;}left;}//更新结果ret max(ret, right - left 1);right;}return ret;}
};
时间复杂度O(n)相比于暴力枚举的O(n^2)提升了不少。
