寺庙招人做网站维护吗,国外做地铁设计的公司网站,软件论坛网站有哪些,怎么用链接进自己做的网站吗题目来源:力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台 本期讲解滑动窗口经典例题,我会从三个点开始讲解题目1.题目解析2.算法原理 3.编写代码
1.题目解析
这道题目理解起来还是比较简单的,我们简单分析一下,也就是给定一个数组,数组是由1和0组成…题目来源:力扣LeetCode官网 - 全球极客挚爱的技术成长平台 本期讲解滑动窗口经典例题,我会从三个点开始讲解题目1.题目解析2.算法原理 3.编写代码
1.题目解析
这道题目理解起来还是比较简单的,我们简单分析一下,也就是给定一个数组,数组是由1和0组成的,给定了你一个条件,可以翻转最多k个0到1,然后让你计算数组中的连续1的最大个数
示例 2.算法详解
这个题目最令人懊恼的就是翻转0这个操作,如果说我们真的去题目中将0改成1的话,代码的复杂量将会上升,极其不好写,所以说我们需要对翻转这个操作进行修改,优化,
题目给定了一个k值,要求翻转的0不能超过k,也就是说我们只需要让寻找的这个区间的0的个数不超过k即可,只要不超过k就说明这个区间的0是一定能够成功翻转成1的,也就不需要真正的进行翻转0的操作了
到此处,我们其实已经可以进行暴力枚举操作了 在枚举的过程中,我们先固定左边的值,再依次枚举所有的可能,可是,在这里我们发现了一个规律,右边的值在每次枚举的时候似乎进行了不必要的操作,每次都要从左边重新开始走,
优化成滑动窗口: 在这里我们用count计算0的个数
我们先让right先走,用right判断,当走到right0的时候,让count,当count3的时候,也就是countk的时候,这里就算出来一个区间了,也就是right-left1,进行接下来的操作,如果这里是暴力解法的话,我们只需要将left然后让right继续进行重复的操作,显然这里浪费了很多时间,
我们可以当count2的时候,让left走,left走到0的时候,让count--,然后进入countk的时候,又让right走判断,直到right走到尾为止 所以现在我们已经发现了两个规律,变成滑动窗口的思想就是如下 3.编写代码
class Solution {
public:int longestOnes(vectorint nums, int k) {int nnums.size();int len0;int zero0;for(int left0,right0;rightn;right){if(nums[right]0)zero;while(zerok){if(nums[left]0){--zero;}left;}lenmax(len,right-left1);}return len;}
};
