当前位置: 首页 > news >正文

算法——滑动窗口(day6)

1004.最大连续1的个数 ||| 

1004. 最大连续1的个数 III - 力扣(LeetCode)

题目解析:

这道题如果能转化为滑动窗口的话就会很简单,因为我们如果尝试去把0翻转为1再计数的话等到第2轮又得重新翻转回来,费时费力~

那么我们不妨默认就把0当作1,选中一段区间只要里面0的个数不超过k那就可以了。这样就把问题转化为求0的个数不超过k的最长子数组,妥妥用滑动窗口。

老规矩,我们先来用暴力找找灵感:

需要列举的有点多,不过也有很多可优化的空间~


算法解析:

其实当我们转换为滑动窗口后相信看过我前边博客的友友们肯定都知道了,所以我们废话不多说。

在right不断遍历的过程中遇到0就记录其个数,等到不满足条件(sum>k)时说明在它之前已经找到最长子数组了。开始新一轮的寻找,这时候我们的right不用再回来遍历,因为之前都已经遍历并记录在sum中了,所以留在原位移动left即可。

 滑动窗口流程:

滑动窗口的两个指针移动规律也很简单:

  • right 遇1——> right++
  • right 遇0——> sum++,right++
  • left 遇1——> left++
  • left 遇0——> sum--,left++

代码: 

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int n = nums.size();int sum = 0;int ret = INT_MIN;for (int left = 0, right = 0; right < n; right++){//扩充窗口if (nums[right] == 0){sum++;}//判断,若sum<=k,到下一循环继续扩充//若sum>k,缩小窗口while (sum > k){if (nums[left] == 0){sum--;}left++;}//更新长度ret = max(ret, right - left + 1);}return ret;}
};

1658.将x减到0的最小操作数 

 1658. 将 x 减到 0 的最小操作数 - 力扣(LeetCode)

题目解析:

这道题从正面来做会很难,因为你要不断考虑是从左边选数还是从右边选数。那么我们不如从另外一个角度来思考这个问题~

首先我们要把通过移除左右两边数使得x==0转换为挑选出左右两区间使得里面的数之和为x.

但两段区间也还是麻烦,我们不妨去挑出处于两区间中间的连续区间。

我们只需要让这个连续区间里面的和为sum-x就可以了,再求出连续区间的长度len,最后n-len反推出真正的最小操作数。


算法解析:

问题转换:求出总数之和为sum-x的最长连续子数组

只要t<a,我们就让right继续往后遍历直到出现t>=a的情况。

而在第二轮开始遍历的时候right其实不用去复位,因为在t>=a的那个节点前面的总和本来就是t<a,left前进一位只会让t更小。所以right是没必要复位的,留在原地就好了。

滑动窗口流程:

最后有一点小细节:

如果题目给的x比我们所有数组之和还大,得特殊处理~ 

代码:

class Solution {
public:int minOperations(vector<int>& nums, int x) {int len = -1;int n = nums.size();int sum = 0;for (int i : nums){sum += i;}//遍历连续数组之和int target = 0;//连续段的期望数值int a = sum - x;//细节处理if (a < 0) return -1;for (int left = 0, right = 0; right < n; right++){//扩充窗口target += nums[right];//判断,只要target>a就缩小窗口,反之就进行下一轮的扩充while (target > a){//缩小窗口target -= nums[left++];}//只有达到期望数值才可以记录长度if (target == a){len = max(len, right - left + 1);}}//没有达到期望数值,说明找不到if (len == -1){return -1;}else{return n - len;}}
};

相关文章:

算法——滑动窗口(day6)

1004.最大连续1的个数 ||| 1004. 最大连续1的个数 III - 力扣&#xff08;LeetCode&#xff09; 题目解析&#xff1a; 这道题如果能转化为滑动窗口的话就会很简单&#xff0c;因为我们如果尝试去把0翻转为1再计数的话等到第2轮又得重新翻转回来&#xff0c;费时费力~ 那么我…...

推荐一款基于Spring Boot 框架开发的分布式文件管理系统,功能齐全,非常便捷(带私活源码)

前言 在数字化时代&#xff0c;文件管理是企业和个人用户的基本需求。然而&#xff0c;现有的文件管理系统往往存在一些痛点&#xff0c;如存储空间有限、文件共享困难、缺乏在线编辑功能、移动端适配性差等。这些问题限制了用户在不同设备和场景下的文件处理能力。 为了解决…...

Mysql-查询

1.基本查询 //查询所有内容 select * from 表名;//查询指定字段 select 字段1&#xff0c;字段2&#xff0c;字段3.....from 表名;//查询时给字段起别名 select 字段1 as 别名1 , 字段2 as 别名2 ... from 表名&#xff1b;//去重查询 select distinct 字段列表 from 表名; …...

广东科学技术职业学院计算机学院领导一行莅临泰迪智能科技参观交流

7月17日&#xff0c;广东科学技术职业学院计算机学院副院长张军、计算机学院副书记吴国庆、计算机学院大数据教学部部长谢文达、科技与校企合作部副部长黄相杰、科技与校企合作部副部长吴胜兵莅临广东泰迪智能科技股份有限公司产教融合实训基地参观交流&#xff0c;泰迪智能科技…...

exo 大模型算力共享;Llama3-70B是什么

目录 exo 大模型算力共享 exo框架的特点 如何使用exo框架 注意事项 结论 Llama3-70B是什么 一、基本信息 二、技术特点 三、性能与应用 四、未来发展 exo 大模型算力共享 exo框架的特点 异构支持:支持多种不同类型的设备,包括智能手机、平板电脑、笔记本电脑以及高…...

测试——Junit

内容大纲: 常用的五个注解 测试用例顺序指定 参数化 测试套件 断言 1. 常用的五个注解 1.1 Test 通常情况下,我们输入要写在main方法下,此时我想直接输出: Test void Test01(){System.out.println("第一个测试用例"); } 1.2 BeforeAll AfterAll BeforeALL在Tes…...

BUG ImportError: cannot import name ‘QAction‘ from ‘PySide6.QtWidgets‘

BUG ImportError: cannot import name ‘QAction’ from ‘PySide6.QtWidgets’ 环境 PySide6 6.7.2详情 在参考 PyQt5 的代码写 Pyside6 的右键菜单时遇到的错误。 错误代码 from PySide6.QtWidgets import QAction错误原因&#xff1a; 在PySdie6中&#xf…...

对某次应急响应中webshell的分析

文章前言 在之前处理一起应急事件时发现攻击者在WEB应用目录下上传了webshell&#xff0c;但是webshell似乎使用了某种加密混淆手法&#xff0c;无法直观的看到其中的木马连接密码&#xff0c;而客户非要让我们连接webshell来证实此文件为后门文件且可执行和利用(也是很恼火&a…...

Vue3新特性

Vue3新特性 1、Composition API1.1 什么是 Composition API1.2 常用 Composition API1.2.1 setup1.2.2 ref1.2.3 reactive1.2.4 computed1.2.5 watchEffect、watchPostEffect、watchSyncEffect1.2.6 watch 2、生命周期2.1 Vue3生命周期钩子2.2 vue2 和 vue3 关于生命周期的对比…...

一套功能齐全、二开友好的即时通讯IM工具,提供能力库和UI库,支持单聊、频道和机器人(附源码)

前言 在当今数字化时代&#xff0c;即时通讯(IM)和实时音视频(RTC)功能已成为众多应用的标配。然而&#xff0c;现有的解-决方案往往存在一些痛点&#xff0c;如架构落后、成本高昂、数据安全性和隐私保护不足&#xff0c;以及二次开发和部署的复杂性。 为了解决这些问题&…...

MySQL:JOIN 多表查询

多表查询 在关系型数据库中&#xff0c;表与表之间是有联系的&#xff0c;它们通过 外键 联系在一起&#xff0c;所以在实际应用中&#xff0c;经常使用多表查询。多表查询就是同时查询两个或两个以上的表。 MySQL多表查询是数据库操作中非常重要的一部分&#xff0c;它允许你…...

【机器学习】必会算法模型之:一文掌握 密度聚类,建议收藏。

密度聚类 1、引言2、密度聚类2.1 定义2.2 核心原理2.3 实现步骤2.4 算法公式2.5 代码示例 3、总结 1、引言 在机器学习的无监督学习领域&#xff0c;聚类是一项基础而重要的任务。 聚类算法通过将数据点分组&#xff0c;使同一组内的数据点具有更大的相似性&#xff0c;而组间…...

代码:前端与数据库交互的登陆界面

<!DOCTYPE html> <html lang"en"> <head> <meta charset"UTF-8"> <meta name"viewport" content"widthdevice-width, initial-scale1.0"> <title>登录</title> </head> <body>…...

发电机基础知识:负载组

什么是发电机负载组&#xff1f; 简单地说&#xff0c;负载组是一种可以产生人工电力负载的设备&#xff0c;用于测试发电机并验证发电机组的性能&#xff0c;包括相关组件&#xff0c;以确保通过使发电机发动机达到适当的工作温度和压力来满足适当的负载。 它是如何工作的&a…...

内网安全:各类密码的抓取

Mimikatz在线读取SAM文件 离线读取SAM文件 在线读取lsass进程 离线读取lsass进程 BrowserGhost浏览器密码抓取 Sharp-HackBrowserData浏览器密码抓取 SharpDecryptPwd数据库密码抓取 LaZagne各类密码的抓取 Windows其他类型抓NTLM Hash工具 sam文件和lsass进程就是Wind…...

前端面试题汇总2

1. CSS 中两个 .class1 .class2 从哪个开始解析 在 CSS 中&#xff0c;选择器 .class1 .class2 表示所有 class 为 class1 的元素中的 class 为 class2 的子元素。浏览器解析这个选择器时&#xff0c;从右向左解析。也就是说&#xff0c;浏览器首先找到所有 class 为 class2 的…...

分布式服务框架zookeeper+消息队列kafka

一、zookeeper概述 zookeeper是一个分布式服务框架&#xff0c;它主要是用来解决分布式应用中经常遇到的一些数据管理问题&#xff0c;如&#xff1a;命名服务&#xff0c;状态同步&#xff0c;配置中心&#xff0c;集群管理等。 在分布式环境下&#xff0c;经常需要对应用/服…...

服务攻防-应用协议cve

Cve-2015-3306 背景&#xff1a; ProFTPD 1.3.5中的mod_copy模块允许远程攻击者通过站点cpfr和site cpto命令读取和写入任意文件。 任何未经身份验证的客户端都可以利用这些命令将文件从文件系统的任何部分复制到选定的目标。 复制命令使用ProFTPD服务的权限执行&#xff0c;…...

Springcloud之gateway的使用详解

官网地址&#xff1a;https://docs.spring.io/spring-cloud-gateway/docs/4.0.4/reference/html/ 1.网关入门 helloword 网关不依赖start-web 导入的pom&#xff1a; <!--gateway--> <dependency><groupIdorg.springframework.cloud</groupId><arti…...

中望CAD 建筑 v2024 解锁版下载、安装教程 (超强的CAD三维制图)

前言 中望CAD建筑版是一款国产CAD制图软件&#xff0c;专注于建筑设计领域。中望CAD建筑版拥有丰富多样的建筑图块和图案&#xff0c;完美兼容各类建筑图纸。同时&#xff0c;它提供了绘图标准规范&#xff0c;使绘图更加规范和专业。更值得一提的是&#xff0c;该软件还具备智…...

MPNet:旋转机械轻量化故障诊断模型详解python代码复现

目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

黑马Mybatis

Mybatis 表现层&#xff1a;页面展示 业务层&#xff1a;逻辑处理 持久层&#xff1a;持久数据化保存 在这里插入图片描述 Mybatis快速入门 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/6501c2109c4442118ceb6014725e48e4.png //logback.xml <?xml ver…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八

现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet&#xff0c;点击确认后如下提示 最终上报fail 解决方法 内核升级导致&#xff0c;需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集&#xff0c;包含8种湿地亚类&#xff0c;该数据以0.5X0.5的瓦片存储&#xff0c;我们整理了所有属于中国的瓦片名称与其对应省份&#xff0c;方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...

Ubuntu Cursor升级成v1.0

0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开&#xff0c;快捷键也不好用&#xff0c;当看到 Cursor 升级后&#xff0c;还是蛮高兴的 1. 下载 Cursor 下载地址&#xff1a;https://www.cursor.com/cn/downloads 点击下载 Linux (x64) &#xff0c;…...