公司网站中新闻中心怎样做优化,百度浏览器电脑版,企业网站建设训,wordpress付费主题分享目录
1. 题目解析
2. 算法原理
3. 代码编写
写在最后#xff1a; 1. 题目解析
题目链接#xff1a;1004. 最大连续1的个数 III - 力扣#xff08;Leetcode#xff09; 这道题不难理解#xff0c;其实就是求出最长的连续是1的子数组#xff0c;
但是#xff0c;他支…目录
1. 题目解析
2. 算法原理
3. 代码编写
写在最后 1. 题目解析
题目链接1004. 最大连续1的个数 III - 力扣Leetcode 这道题不难理解其实就是求出最长的连续是1的子数组
但是他支持了一个操作就是可以翻转k个0变成1。
这个条件一出来这道题的难度就上来了情况变得比较的复杂。
2. 算法原理
然后我们就可以想一想应该怎么抽象出一条规则
将这个问题转化成找出最长的子数组0的个数不超过k个即可
如果使用暴力枚举思路还是比较简单的。
基于暴力枚举我们可以使用滑动窗口来优化这道题
其实最难的一步转化问题我们已经做完了我们只需要根据这个思路设计滑动窗口即可
我们维护一个窗口
当0的数量小于2的时候不断扩大窗口
当0的数量等于2的时候我们记录最长的子数组
当0的数量大于2的时候我们缩小窗口直到0的数量小于等于2
来看代码
3. 代码编写
class Solution {
public:int longestOnes(vectorint nums, int k) {unordered_mapint, int win;int len 0, left 0, right 0;while(right nums.size()) {len max(len, right - left);win[nums[right]];while(left nums.size() win[0] k) {win[nums[left]]--;}}len max(len, right - left);return len;}
};
写在最后
以上就是本篇文章的内容了感谢你的阅读。
如果感到有所收获的话可以给博主点一个赞哦。
如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~
