【滑动窗口】leetcode1004:最大连续1的个数
一.题目描述
最大连续1的个数

这道题要我们找最大连续1的个数,看到“连续”二字,我们要想到滑动窗口的方法。滑动窗口的研究对象是一个连续的区间,这个区间需要满足某个条件。那么本题要找的是怎样的区间呢?是一个通过翻转0后得到连续1的区间,而最多可以翻转k个字符。
故要找的是包含0的个数不超过k的区间,因为如果超过k个0,即使经过翻转,该区间的1也还是不连续。
题意转化过来后,本题便不再困难。
二.思路分析
滑动窗口是在暴力解法的基础上优化过来的。本题的暴力解法就是两层for循环枚举所有的区间,找出满足条件的区间,通过比较得到最长的区间长度,结果就是数组中连续1的最大个数。
class Solution {
public:int longestOnes(vector<int>& 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.进窗口之后,zero>=k,符合要求
2.进窗口之后,zero<k,经过若干次出窗口操作后,zero=k ,满足要求
故更新结果应放在整个循环的最后面
class Solution {
public:int longestOnes(vector<int>& 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)提升了不少。
相关文章:
【滑动窗口】leetcode1004:最大连续1的个数
一.题目描述 最大连续1的个数 这道题要我们找最大连续1的个数,看到“连续”二字,我们要想到滑动窗口的方法。滑动窗口的研究对象是一个连续的区间,这个区间需要满足某个条件。那么本题要找的是怎样的区间呢?是一个通过翻转0后得到…...
力扣:73. 矩阵置零(Python3)
题目: 给定一个 m x n 的矩阵,如果一个元素为 0 ,则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。 来源:力扣(LeetCode) 链接:力扣(LeetCode)官网 - 全球极客挚…...
VB|基础语法 变量定义 函数定义 循环语句 IF判断语句等
文章目录 变量定义函数定义控制台输入输出switch case语句IF语句FOR循环语句不等于逻辑运算符 变量定义 int Dim 变量名 As Int32 0 string Dim 变量名 As String "" bool Dim 变量名 As Boolean False 枚举 Dim 变量名 As 枚举名 数组 Dim array(256) As String…...
Github 博客搭建
Github 博客搭建 准备工作 准备一个 github 账号;建立 github 仓库,仓库名为 username.github.io,同时设置仓库为 public;clone 仓库,写入一个 index.html 文件,推送到仓库(许多网上的教程会有…...
模型预测笔记(三):通过交叉验证网格搜索机器学习的最优参数
文章目录 网络搜索介绍步骤参数代码实现 网络搜索 介绍 网格搜索(Grid Search)是一种超参数优化方法,用于选择最佳的模型超参数组合。在机器学习中,超参数是在训练模型之前设置的参数,无法通过模型学习得到。网格搜索…...
创建型模式-建造者模式
使用多个简单的对象一步一步构建成一个复杂的对象 主要解决:主要解决在软件系统中,有时候面临着"一个复杂对象"的创建工作,其通常由各个部分的子对象用一定的算法构成;由于需求的变化,这个复杂对象的各个部…...
Rust常用加密算法
哈希运算(以Sha256为例) main.rs: use crypto::digest::Digest;use crypto::sha2::Sha256;fn main() { let input "dashen"; let mut sha Sha256::new(); sha.input_str(input); println!("{}", sha.result_str());} Cargo.toml: [package]n…...
[管理与领导-55]:IT基层管理者 - 扩展技能 - 1 - 时间管理 -2- 自律与自身作则,管理者管好自己时间的五步法
前言: 管理好自己的时间,不仅仅是理念,也是方法和流程。 步骤1:理清各种待办事项 当提到工作事项时,这通常指的是要完成或处理的工作任务或事务。这些事项可以包括以下内容: 任务分配:根据工作…...
电子商务员考试题库及答案(中级)--判断题
电子商务员题库 一、判断题 1.EDI就是按照商定的协议,将商业文件分类,并通过计算机网络,在贸易伙伴的计算机网络系统之间进行数据交换和自动处理。〔〕 2.相互通信的EDI的用户必须使用相同类型的计算机。〔 〕 3.EDI采用共同…...
(WAF)Web应用程序防火墙介绍
(WAF)Web应用程序防火墙介绍 1. WAF概述 Web应用程序防火墙(WAF)是一种关键的网络安全解决方案,用于保护Web应用程序免受各种网络攻击和威胁。随着互联网的不断发展,Web应用程序变得越来越复杂&#x…...
SpringMVC拦截器常见应用场景
在Spring MVC中,拦截器是通过实现HandlerInterceptor接口来定义的。该接口包含了三个方法: preHandle:在请求到达处理器之前执行,可以进行一些预处理操作。如果返回false,则请求将被拦截,不再继续执行后续的…...
爬虫:绕过5秒盾Cloudflare和DDoS-GUARD
本文章仅供技术研究参考,勿做它用! 5秒盾的特点 <title>Just a moment...</title> 返回的页面中不是目标数据,而是包含上面的代码:Just a moment... 或者第一次打开网页的时候: 这几个特征就是被Cloud…...
数据仓库环境下的超市进销存系统结构
传统的进销存系统建立的以单一数据库为中心的数据组织模式,已经无 法满足决策分析对数据库系统的要求,而数据仓库技术的出现和发展,为上述问题 的解决提供了强有力的工具和手段。数据仓库是一种对多个分布式的、异构的数据 库提供统一查询…...
leetcode:2011. 执行操作后的变量值(python3解法)
难度:简单 存在一种仅支持 4 种操作和 1 个变量 X 的编程语言: X 和 X 使变量 X 的值 加 1--X 和 X-- 使变量 X 的值 减 1 最初,X 的值是 0 给你一个字符串数组 operations ,这是由操作组成的一个列表,返回执行所有操作…...
ubuntu下mysql
安装: sudo apt update sudo apt install my_sql 安装客户端: sudo apt-get install mysql-client sudo apt-get install libmysqlclient-dev 启动服务 启动方式之一: sudo service mysql start 检查服务器状态方式之一:sudo …...
大模型从入门到应用——LangChain:链(Chains)-[链与索引:检索式问答]
分类目录:《大模型从入门到应用》总目录 下面这个示例展示了如何在索引上进行问答: from langchain.embeddings.openai import OpenAIEmbeddings from langchain.vectorstores import Chroma from langchain.text_splitter import CharacterTextSplitte…...
【LeetCode-中等题】142. 环形链表 II
文章目录 题目方法一:哈希表set去重方法二:快慢指针 题目 方法一:哈希表set去重 思路:我们遍历链表中的每个节点,并将它记录下来;一旦遇到了此前遍历过的节点,就可以判定链表中存在环。借助哈希…...
Android TV开发之VerticalGridView
Android TV应用开发和手机应用开发是一样的,只是多了焦点控制,即选中变色。 androidx.leanback.widget.VerticalGridView 继承 BaseGridView , BaseGridView 继承 RecyclerView 。 所以 VerticalGridView 就是 RecyclerView ,使…...
SpringBoot+Vue项目添加腾讯云人脸识别
一、引言 人脸识别是一种基于人脸特征进行身份认证和识别的技术。它使用计算机视觉和模式识别的方法,通过分析图像或视频中的人脸特征,例如脸部轮廓、眼睛、鼻子、嘴巴等,来验证一个人的身份或识别出他们是谁。 人脸识别可以应用在多个领域…...
什么是IPv4?什么又是IPv6?
IPv4网络IPv4地址 IPv6网络IPv6地址 路由总结感谢 💖 hello大家好😊 IPv4网络 IPv4(Internet Protocol Version 4)是当今互联网上使用的主要网络协议。 IPv4地址 IPv4 地址有32位,通常使用点号分隔的四个十进制八位…...
基于算法竞赛的c++编程(28)结构体的进阶应用
结构体的嵌套与复杂数据组织 在C中,结构体可以嵌套使用,形成更复杂的数据结构。例如,可以通过嵌套结构体描述多层级数据关系: struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...
深入剖析AI大模型:大模型时代的 Prompt 工程全解析
今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以? 在 Golang 的面试中,map 类型的使用是一个常见的考点,其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...
Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务
通过akshare库,获取股票数据,并生成TabPFN这个模型 可以识别、处理的格式,写一个完整的预处理示例,并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务,进行预测并输…...
【JavaSE】绘图与事件入门学习笔记
-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角,以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向,距离坐标原点x个像素;第二个是y坐标,表示当前位置为垂直方向,距离坐标原点y个像素。 坐标体系-像素 …...
代理篇12|深入理解 Vite中的Proxy接口代理配置
在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...
关键领域软件测试的突围之路:如何破解安全与效率的平衡难题
在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件,这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下,实现高效测试与快速迭代?这一命题正考验着…...
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列,以便知晓哪些列包含有价值的数据,…...
C语言中提供的第三方库之哈希表实现
一. 简介 前面一篇文章简单学习了C语言中第三方库(uthash库)提供对哈希表的操作,文章如下: C语言中提供的第三方库uthash常用接口-CSDN博客 本文简单学习一下第三方库 uthash库对哈希表的操作。 二. uthash库哈希表操作示例 u…...
MySQL 主从同步异常处理
阅读原文:https://www.xiaozaoshu.top/articles/mysql-m-s-update-pk MySQL 做双主,遇到的这个错误: Could not execute Update_rows event on table ... Error_code: 1032是 MySQL 主从复制时的经典错误之一,通常表示ÿ…...
