算法练习:1004. 最大连续1的个数 III

题目链接:1004. 最大连续1的个数 III。

题目要求,给定一个数组,这个数组里面只有0或1,然后计算有多少个连续的1的最大长度,同时给了一个条件就是,可以把k个0变成1,然后来计算长度。

暴力解法:枚举每一个子数组,记录连续为1的长度,同时用一个计数器cut来统计0的个数。

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int n = nums.size();int sum = INT_MIN;for(int i = 0;i < n;i++){int cut = 0;int sum1 = 0;for(int j = i;j < n;j++){if(nums[j] == 0){cut++;}if(cut == k+1){break;}sum1++;}sum = sum1 > sum ? sum1 : sum;}return sum;}
};

但是暴力解法会超时!!!

在暴力解法前提下进行对代码的优化:

  • 通过定义两个指针来控制,left固定在第一个位置,right进行移动,定义cut当计数器
  • 如果right对应值为1,则无视,直接++
  • 如果right对应值为0,则cut++,right也++
  • 判断,如果cut > k,则开始移动left
  • 如果left对应值为1,无视,直接++
  • 如果对应值为0,则cut--,left也++
  • 判断完就进行更新长度

为什么判断cut > k后要进行移动left,而right不动,因为left到right之间0的个数已经超过k,此时right在回到left位置重新进行检测长度,没有必要,因为重新检测的长度肯定比之前长度短,所以只需要更新left,更新到cut=k的位置,然后再进行移动right。

这样同向双指针操作叫做滑动窗口。

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int left = 0,right = 0,cut = 0;int n = nums.size();int ret = 0;while(left<n && right < n){if(nums[right] == 0) cut++;while(cut > k){if(nums[left] == 0) cut--;left++;}ret = max(ret , right - left + 1);right++;}return ret;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/467134.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

CCS下载安装(以12.3.0版本为例)

Code Composer Studio 是一个集成开发环境 (IDE)&#xff0c;简称CCS软件。支持 TI 的微控制器和嵌入式处理器产品的开发。Code Composer Studio 包含一整套用于开发和调试嵌入式应用程序的工具。 CCS9.3.0及以上版本不需要License文件&#xff0c;但是CCS旧版本比如CCS5.5.0需…

串口接收,不定长数据接收

###1.CUBE-MX配置串口 2.我采用串口中断接收&#xff0c;打开中断接口 3.时钟同样8倍频&#xff0c;1分频&#xff0c;使用内部时钟 打开串口中断 main() { __HAL_UART_ENABLE_IT(&huart1, UART_IT_IDLE); // 启用空闲中断__HAL_UART_ENABLE_IT(&huart1, UART_IT_R…

密码学知识点整理二:常见的加密算法

常用的加密算法包括对称加密算法、非对称加密算法和散列算法。 对称加密算法 AES&#xff1a;高级加密标准&#xff0c;是目前使用最广泛的对称加密算法之一&#xff0c;支持多种密钥长度&#xff08;128位、192位、256位&#xff09;&#xff0c;安全性高&#xff0c;加密效率…

MongoDB Shell 基本命令(三)聚合管道

管道含义 类似Linux中的管道&#xff0c;前一个命令的输出作为后一个命令的输入。 显示网络连接、路由表和网络接口统计信息 netstat -ano -netstat:network statistics 网络统计 -a:显示所有连接和监听端口&#xff0c;包括所有活动的TCP和UDP连接。 -n:以数字形式显示地址…

OpenCV相机标定与3D重建(1)概述

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 本节中的函数使用所谓的针孔相机模型。通过使用透视变换将场景中的3D点 P w P_w Pw​ 投影到图像平面上&#xff0c;从而获得场景的视图&#x…

Docker部署Oracle 11g

1&#xff0c;拉取镜像&#xff1a; sudo docker pull registry.cn-hangzhou.aliyuncs.com/helowin/oracle_11gsudo docker images 2&#xff0c;启动一个临时容器&#xff0c;用于拷贝数据库文件&#xff0c;挂载到宿主主机&#xff0c;使数据持久化&#xff1a; sudo docke…

【Linux系统】—— 基本指令(二)

【Linux系统】—— 基本指令&#xff08;二&#xff09; 1 「alias」命令1.1 「ll」命令1.2 「alias」命令 2 「rmdir」指令与「rm」指令2.1 「rmdir」2.2 「rm」2.2.1 「rm」 删除普通文件2.2.2 「rm」 删除目录2.2.3 『 * 』 通配符 3 「man」 指令4 「cp」 指令4.1 拷贝普通…

从单层到 MVC,再到 DDD:架构演进的思考与实践

引言 在日常开发中&#xff0c;我们之前工作中经常接手的大多数都是传统 MVC 架构体系的项目。然而&#xff0c;随着现在分布式和微服务架构的普及&#xff0c;越来越多的项目开始重构、拆分&#xff0c;传统的 MVC 架构也逐渐向 DDD 架构演进。为什么需要将传统架构重构为 DD…

贝式计算的 AI4S 观察:使用机器学习对世界进行感知与推演,最大魅力在于横向扩展的有效性

「传统研究方法高度依赖于科研人员自身的特征和问题定义能力&#xff0c;通常采用小数据&#xff0c;在泛化能力和拓展能力上存疑。而 AI 研究方法则需要引入大规模、高质量数据&#xff0c;并采用机器学习进行特征抽取&#xff0c;这使得产生的科研结果在真实世界的问题中非常…

[产品管理-58]:安索夫矩阵矩阵帮助创业者确定研发出来的产品在市场中定位策略

目录 一、提出背景 二、核心思想与结构 三、应用背景与领域 四、实践案例 安索夫矩阵&#xff08;Ansoff Matrix&#xff09;&#xff0c;也被称为产品/市场方格或成长矢量矩阵&#xff0c;其应用背景可以从以下几个方面进行详细阐述&#xff1a; 一、提出背景 安索夫矩阵…

安当ASP系统:适合中小企业的轻量级Radius认证服务器

安当ASP&#xff08;Authentication Service Platform&#xff09;身份认证系统是一款功能强大的身份认证服务平台&#xff0c;特别适用于中小企业。其中&#xff0c;简约型Radius认证服务器是安当ASP系统中的一个重要组成部分。以下是对该系统的详细介绍&#xff1a; 一、主要…

uniapp配置h5路由模式为history时404

为了不让URL中出现#&#xff0c;让uniapp项目配置h5路由模式为hisory 然而本地好好的&#xff0c;放到服务器上却404了。 解决方法是给nginx配置一个伪静态&#xff1a; location /xxx-html/ {alias /home/nginx_web/xxx_new_html/;try_files $uri $uri/ /xxx-html/index.ht…

Go-HTTP框架设计实现概述

1.再谈HTTP协议 第一个大规模使用&#xff1a;HTTP0.9 三十多年了 HTTP:超文本传输协议&#xff08;Hypertext Transfer Protocal&#xff09; 为什么是超文本&#xff1a;因为图片、音乐、视频是文本的扩充 为什么需要协议&#xff1a;约定俗称的规则&#xff08;像说话&…

使用Matlab建立决策树

综述 除了神经网络模型以外&#xff0c;树模型及基于树的集成学习模型是较为常用的效果较好的预测模型。我们以下先构建一个决策树模型。 决策树算法的优点如下&#xff1a;1、 决策树易于理解和实现&#xff0c;用户在学习过程中不需要了解过多的背景知识&#xff0c;其能够…

【JavaSE】(3)数组

目录 一、数组的定义和初始化 1. 什么是数组 2. 数组的定义 3. 数组的初始化 4. 操作数组的工具包 二、数组的使用 三、引用类型 1. JVM内存分布 2. 引用变量 3. 默认值 null 四、二维数组 1. 二维数组的定义和初始化 2. 不规则的二维数组 一、数组的定义和初始化…

uniapp—android原生插件开发(3Android真机调试)

本篇文章从实战角度出发&#xff0c;将UniApp集成新大陆PDA设备RFID的全过程分为四部曲&#xff0c;涵盖环境搭建、插件开发、AAR打包、项目引入和功能调试。通过这份教程&#xff0c;轻松应对安卓原生插件开发与打包需求&#xff01; 一、打包uniapp资源包&#xff1a; 打包…

【 AI写作鹅-注册安全分析报告-无验证方式导致安全隐患】

前言 由于网站注册入口容易被黑客攻击&#xff0c;存在如下安全问题&#xff1a; 1. 暴力破解密码&#xff0c;造成用户信息泄露 2. 短信盗刷的安全问题&#xff0c;影响业务及导致用户投诉 3. 带来经济损失&#xff0c;尤其是后付费客户&#xff0c;风险巨大&#xff0c;造…

esp32学习:利用虫洞ESP32开发板,快速实现无线图传

我们的虫洞开发板&#xff0c;能够完美运行esp who AI代码&#xff0c;所以实现无线图传那是非常容易的&#xff0c;我们先看看examples目录&#xff1a; 里面有比较多的web例程&#xff0c;在这些例程下&#xff0c;稍作修改&#xff0c;就可以快速实现我的图传无线功能&#…

Docker网络概述

1. Docker 网络概述 1.1 网络组件 Docker网络的核心组件包括网络驱动程序、网络、容器以及IP地址管理&#xff08;IPAM&#xff09;。这些组件共同工作&#xff0c;为容器提供网络连接和通信能力。 网络驱动程序&#xff1a;Docker支持多种网络驱动程序&#xff0c;每种驱动程…

RK3568平台开发系列讲解(设备树篇)设备树中CPU描述

🚀返回专栏总目录 文章目录 一、CPU节点1.1、节点结构:1.2、处理器属性:1.3、 处理器拓扑关系:二、cpu-map、 socket、 cluster 节点三、core、 thread 节点沉淀、分享、成长,让自己和他人都能有所收获!😄 一、CPU节点 设备树的 cpus 节点是用于描述系统中的处理器的一…