【OJ刷题】同向双指针问题3
✨ 个人主页:在线OJ的阿川
💖文章专栏:OJ刷题入门到进阶
🌏代码仓库:
写在开头
现在您看到的是我的结论或想法,但在这背后凝结了大量的思考、经验和讨论
目录
- 1. 题目介绍
- 2. 题目拆解
- 3. 具体详情
- 4. 具体代码
1. 题目介绍
难度:中
题目练习:最大连续1的个数 III
题目信息:给定一个二进制数组 nums 和一个整数 k,假设最多可以翻转 k 个 0 ,则返回执行操作后 数组中连续 1 的最大个数 。
举个例子: 具体如图1所示
图1 举个例子
2. 题目拆解
本质上:观察规律,利用滑动窗口
特点是:同向双指针,不存在回退
解决方法:同向双指针算法,如图2所示
图2 同向双指针
3. 具体详情
1. 利用双指针构建滑动窗口
2. 循环加零计数器进行判断及出窗口
3. max更新结果
4. 具体代码
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int len = 0;
for(int left = 0, right = 0, n = nums.size(), zero = 0; right < n; right++) //双指针滑动窗口以及零计数器
{
if(0 == nums[right]) zero++; //添加零计数
while(zero > k) //利用零计数器加循环来判断及出窗口
{
if(0 == nums[left++]) zero--;
}
len = max(len, right - left + 1); //利用max更新结果
}
return len;
}
5. 夹带私货
若你能看到看到这篇文章且能看到这,则说明你我有缘,留个关注吧,后面还会接着计算机408、底层原理、开源项目、以及数据、后端研发相关、实习、笔试/面试、秋招/春招、各种竞赛相关、简历相关、考研、学术相关……,祝你我变得更强
原文地址:https://blog.csdn.net/2301_81874719/article/details/145145458
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/503688.html 如若内容造成侵权/违法违规/事实不符,请联系邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/503688.html 如若内容造成侵权/违法违规/事实不符,请联系邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!