滑动窗口--(中篇)
将X减到0的最小操作数

给你一个整数数组 nums 和一个整数 x 。每一次操作时,你应当移除数组 nums 最左边或最右边的元素,然后从 x 中减去该元素的值。请注意,需要 修改 数组以供接下来的操作使用。
如果可以将 x 恰好 减到 0 ,返回 最小操作数 ;否则,返回 -1 。
示例 1:
输入:nums = [1,1,4,2,3], x = 5
输出:2
解释:最佳解决方案是移除后两个元素,将 x 减到 0 。
示例 2:
输入:nums = [5,6,7,8,9], x = 4
输出:-1
示例 3:
输入:nums = [3,2,20,1,1,3], x = 10
输出:5
解释:最佳解决方案是移除后三个元素和前两个元素(总共 5 次操作),将 x 减到 0 。
提示:
1 <= nums.length <= 1051 <= nums[i] <= 104- `1 <= x <= 109


这里我们可能会觉得正着做去求,会有些困难,可以尝试着反着来做,效果会不一样
算法思路:
题⽬要求的是数组「左端+右端」两段连续的、和为 x 的最短数组,信息量稍微多⼀些,不易理清 思路;我们可以转化成求数组内⼀段连续的、和为 sum(nums) - x 的最⻓数组。此时,就是熟 悉的「滑动窗⼝」问题了。
算法流程:
a. 转化问题:求 target = sum(nums) - x 。如果 target < 0 ,问题⽆解;
b. 初始化左右指针 left = 0 , right = 0 (滑动窗⼝区间表⽰为 [left, right) ,左右区间是否开闭很重 要,必须设定与代码⼀致),记录当前滑动窗⼝内数组和的变量 tmp= 0 ,记录当前满⾜条 件数组的最⼤区间⻓度ret = -1 ;
c. 当 right ⼩于等于数组⻓度时,⼀直循环:
i. 如果 sum < target ,右移右指针,直⾄变量和⼤于等于 target ,或右指针已经移到 头;
ii. 如果 sum > target ,右移左指针,直⾄变量和⼩于等于 target ,或左指针已经移到 头;
iii. 如果经过前两步的左右移动使得 sum == target ,维护满⾜条件数组的最⼤⻓度,并 让下个元素进⼊窗⼝;
d. 循环结束后,如果 ret 的值有意义,则计算结果返回;否则,返回 -1 。
代码如下:
class Solution {
public:int minOperations(vector<int>& nums, int x) {int sum=0;for(int a:nums) sum+=a;int target=sum-x;if(target<0) return -1;int ret=-1;for(int left=0,right=0,tmp=0;right<nums.size();right++){tmp+=nums[right];while(tmp>target)tmp-=nums[left++];if(tmp==target)ret=max(ret,right-left+1);}if(ret==-1)return ret;else return nums.size()-ret;}
};
水果成篮
你正在探访一家农场,农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示,其中 fruits[i] 是第 i 棵树上的水果 种类 。
你想要尽可能多地收集水果。然而,农场的主人设定了一些严格的规矩,你必须按照要求采摘水果:
- 你只有 两个 篮子,并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
- 你可以选择任意一棵树开始采摘,你必须从 每棵 树(包括开始采摘的树)上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次,你将会向右移动到下一棵树,并继续采摘。
- 一旦你走到某棵树前,但水果不符合篮子的水果类型,那么就必须停止采摘。
给你一个整数数组 fruits ,返回你可以收集的水果的 最大 数目。
示例 1:
输入:fruits = [1,2,1]
输出:3
解释:可以采摘全部 3 棵树。
示例 2:
输入:fruits = [0,1,2,2]
输出:3
解释:可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘,则只能采摘 [0,1] 这两棵树。
示例 3:
输入:fruits = [1,2,3,2,2]
输出:4
解释:可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘,则只能采摘 [1,2] 这两棵树。
示例 4:
输入:fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出:5
解释:可以采摘 [1,2,1,1,2] 这五棵树。
提示:
1 <= fruits.length <= 1050 <= fruits[i] < fruits.length
题目解析
转化成找出一个最长的子数组的长度,子数组中不能超过两种水果的类型

算法思路:**
研究的对象是⼀段连续的区间,可以使⽤「滑动窗⼝」思想来解决问题。
让滑动窗⼝满⾜:窗⼝内⽔果的种类只有两种。
做法:右端⽔果进⼊窗⼝的时候,⽤哈希表统计这个⽔果的频次。这个⽔果进来后,判断哈希表的 ⼤⼩:
▪ 如果⼤⼩超过 2:说明窗⼝内⽔果种类超过了两种。那么就从左侧开始依次将⽔果划出窗 ⼝,直到哈希表的⼤⼩⼩于等于 2,然后更新结果;
▪ 如果没有超过 2,说明当前窗⼝内⽔果的种类不超过两种,直接更新结果 ret。
算法流程:
a. 初始化哈希表 hash 来统计窗⼝内⽔果的种类和数量;
b. 初始化变量:左右指针 left = 0,right = 0,记录结果的变量 ret = 0;
c. 当 right ⼩于数组⼤⼩的时候,⼀直执⾏下列循环:
i. 将当前⽔果放⼊哈希表中;
ii. 判断当前⽔果进来后,哈希表的⼤⼩:
• 如果超过 2:
◦ 将左侧元素滑出窗⼝,并且在哈希表中将该元素的频次减⼀;
◦ 如果这个元素的频次减⼀之后变成了 0,就把该元素从哈希表中删除;
◦ 重复上述两个过程,直到哈希表中的⼤⼩不超过 2;
iii. 更新结果 ret;
iv. right++,让下⼀个元素进⼊窗⼝;
d. 循环结束后,ret 存的就是最终结果。
C++ 算法代码(使⽤容器):
class Solution
{
public:int totalFruit(vector<int>& f) {unordered_map<int, int> hash; // 统计窗⼝内出现了多少种⽔果int ret = 0;for(int left = 0, right = 0; right < f.size(); right++){hash[f[right]]++; // 进窗⼝while(hash.size() > 2) // 判断{// 出窗⼝
hash[f[left]]--;if(hash[f[left]] == 0)hash.erase(f[left]);left++;}ret = max(ret, right - left + 1);}return ret;}
};
但是一直插入和删除的时间复杂度会提高,所以根据题目提示是有范围的,可以考虑用数组来模拟哈希表
代码如下(⽤数组模拟哈希表):
class Solution {
public:int totalFruit(vector<int>& fruits) {int hash[100001]={0};int ret=0;for(int left=0,right=0,kinds=0;right<fruits.size();right++){if(hash[fruits[right]]==0) kinds++;hash[fruits[right]]++;while(kinds>2){hash[fruits[left]]--;if(hash[fruits[left]]==0) kinds--;left++;}ret=max(ret,right-left+1);}return ret;}
};
相关文章:
滑动窗口--(中篇)
将X减到0的最小操作数 给你一个整数数组 nums 和一个整数 x 。每一次操作时,你应当移除数组 nums 最左边或最右边的元素,然后从 x 中减去该元素的值。请注意,需要 修改 数组以供接下来的操作使用。 如果可以将 x 恰好 减到 0 ,返…...
Java性能调优:实战技巧与最佳实践
引言 Java作为企业级应用开发的首选语言之一,其性能直接影响到系统的响应速度和用户体验。性能调优是一项复杂的工作,涉及多个层面的知识和技术。本文将通过具体的示例,探讨一些常见的性能调优技巧及最佳实践。 1. 了解你的应用程序 示例&…...
排版套料系统设计说明
先上效果图 项目地址 1.产品介绍 产品名称:StreamFit 智能排版套料系统 主要功能: 智能排版优化 功能描述:StreamFit 利用先进的算法技术,自动对各类材料(如布料、金属板材、纸张等)进行高效排版布局&am…...
算法修炼之路之二分查找
目录 一:三大二分介绍及模板 1.普通二分 2.查找左右边界的二分及模板 二:LeetCode OJ练习 1.第一题 2.第二题 3.第三题 4.第四题 5.第五题 6.第六题 一:三大二分介绍及模板 1.普通二分 这里通过一道题来引出普通二分及模板 LeetCode_704 二分查找 画图分析: 具体代…...
OpenAI预计明年将推出“代理”系统
每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗?订阅我们的简报,深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同,从行业内部的深度分析和实用指南中受益。不要错过这个机会,成为AI领…...
每日OJ题_牛客_重排字符串_贪心_C++_Java
目录 牛客_重排字符串_贪心 题目解析 C代码 Java代码 牛客_重排字符串_贪心 重排字符串 (nowcoder.com) 描述: 小红拿到了一个只由小写字母组成的字符串。她准备把这个字符串重排(只改变字母的顺序,不改变数量) …...
Python 进阶部分详细整理
1. 面向对象编程(OOP) 面向对象编程 (OOP) 是一种通过将程序中的数据和功能封装为对象的编程范式。OOP 基于四个核心概念:类与对象、继承、封装与多态。 类与对象 类(Class):类是创建对象的蓝图或模板。它…...
[ RK3566-Android11 ] 关于移植 RK628F 驱动以及后HDMI-IN图像延迟/无声等问题
问题描述 由前一篇文章https://blog.csdn.net/jay547063443/article/details/142059700?fromshareblogdetail&sharetypeblogdetail&sharerId142059700&sharereferPC&sharesourcejay547063443&sharefromfrom_link,移植HDMI-IN部分驱动后出现&a…...
【黑马点评】 使用RabbitMQ实现消息队列——2.使用RabbitMQ监听秒杀下单
2 使用RabbitMQ实现消息队列 2.1 修改\hm-dianping\pom.xmlpom.xml文件 添加RabbitMQ的环境 <!-- RabbitMQ--> <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-amqp</artifactId> </depe…...
业务封装与映射 -- OTUk/ODUk/OPUk开销帧结构
开销是为了保证净荷正常、灵活传送所必须附加的供网络运行、管理和维护(OAM)使用的字节。 OTN电层开销包括OTUk开销、ODUk开销、OPUk开销、OTUCn开销、ODUCn开销、OPUCn开销和帧对齐开销。 SM开销属于OTU开销,占用3个字节;PM开销…...
Vim基本用法
Vim用法 一、基本模式 1. 普通模式(Normal Mode) 移动光标 基本移动:使用方向键(h左移、j下移、k上移、l右移),也可以使用 H(移到屏幕顶部)、M(移到屏幕中间ÿ…...
python 实现Tarjan 用于在有向图中查找强连通分量的算法
Tarjan 用于在有向图中查找强连通分量的算法介绍 Tarjan算法是一种用于在有向图中查找强连通分量的高效算法,由Robert Tarjan在1972年提出。强连通分量是指在有向图中,如果从顶点u到顶点v以及从顶点v到顶点u都存在一条路径,那么顶点u和顶点v…...
Qt开发技巧(十五)字符串去除空格,跨网段搜索不生效,设置图片显示失败问题,表格视图的批量删除,主动判断字串编码,开启向前查询的属性,画家类载入html来绘制
继续讲一些Qt开发中的技巧操作: 1.字符串去除空格 我们经常会遇到字符串重去除空格的情况,对于QString去除空格,有多种场景,可能需要去除左侧、右侧、所有等位置的空格; //字符串去空格 -1移除左侧空格 0移除所有空格…...
【机器学习】智驭未来:探索机器学习在食品生产中的革新之路
📝个人主页🌹:Eternity._ 🌹🌹期待您的关注 🌹🌹 ❀目录 🔍1. 引言:探索机器学习在食品生产中的革新之路📒2. 机器学习在食品质量控制中的应用🌞实…...
Ubuntu 安装CUDA并使用Docker配置Pytorch环境
文章目录 参考安装顺序Nvidia GPU driverDockerNvidia Container ToolkitDocker PyTorch 1. Nvidia GPU Driver2. Docker 安装(使用apt存储库进行安装)3. Nvidia Container Toolkit3.1 Docker测试GPU 参考 安装顺序 Nvidia GPU driver Docker Nvidia…...
【论文阅读】Simulating 500 million years of evolution with a language model
Simulating 500 million years of evolution with a language model 1、概述 展示了语言模型在蛋白质设计和进化模拟方面的能力。通过对 ESM3 模型的研究,发现其能够生成与自然蛋白质差异较大且具有功能的新蛋白质,如新型绿色荧光蛋白(GFP),表明语言模型可以达到自然进化…...
detectron2/layers源码笔记
from .wrappers import ( BatchNorm2d, Conv2d, #在torch.conv2d的基础上集成了norm层和activation层 ConvTranspose2d, cat, interpolate, Linear, nonzero_tuple, #nonzero_tuple(x)得到tuple of 每个维度的索引 cross_entropy, empty_input_loss_func…...
LLM+知识图谱新工具! iText2KG:使用大型语言模型构建增量知识图谱
iText2KG是一个基于大型语言模型的增量知识图谱构建工具,通过从文本文档中提取实体和关系来逐步构建知识图谱。该工具具有零样本学习能力,能够在无需特定训练的情况下,在多个领域中进行知识提取。它包括文档提炼、实体提取和关系提取模块&…...
React基础-快速梳理
React介绍 React由Meta公司开发,是一个用于构建Web和原生交互界面的库 React的优势 相较于传统基于DOM开发的优势 组件化的开发方式不错的性能 相较于其它前端框架的优势 丰富的生态跨平台支持 开发环境创建 create-react-app是一个快速创建React开发环境的…...
H.264编解码 - NALU详解
一、概述 NALU(Network Abstraction Layer Unit)是H.264编解码中的一个重要概念。H.264是一种视频压缩标准,将视频数据分割成一系列的NALU。每个NALU都是一个独立的数据单元,包含视频压缩后的一个片段。每个NALU都有自己的起始码和长度前缀,用于标识NALU的起始位置和长度。…...
【单片机期末】单片机系统设计
主要内容:系统状态机,系统时基,系统需求分析,系统构建,系统状态流图 一、题目要求 二、绘制系统状态流图 题目:根据上述描述绘制系统状态流图,注明状态转移条件及方向。 三、利用定时器产生时…...
TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案
一、TRS收益互换的本质与业务逻辑 (一)概念解析 TRS(Total Return Swap)收益互换是一种金融衍生工具,指交易双方约定在未来一定期限内,基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...
IT供电系统绝缘监测及故障定位解决方案
随着新能源的快速发展,光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域,IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选,但在长期运行中,例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...
智能仓储的未来:自动化、AI与数据分析如何重塑物流中心
当仓库学会“思考”,物流的终极形态正在诞生 想象这样的场景: 凌晨3点,某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径;AI视觉系统在0.1秒内扫描包裹信息;数字孪生平台正模拟次日峰值流量压力…...
Device Mapper 机制
Device Mapper 机制详解 Device Mapper(简称 DM)是 Linux 内核中的一套通用块设备映射框架,为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程,并配以详细的…...
Yolov8 目标检测蒸馏学习记录
yolov8系列模型蒸馏基本流程,代码下载:这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中,**知识蒸馏(Knowledge Distillation)**被广泛应用,作为提升模型…...
PostgreSQL——环境搭建
一、Linux # 安装 PostgreSQL 15 仓库 sudo dnf install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-$(rpm -E %{rhel})-x86_64/pgdg-redhat-repo-latest.noarch.rpm# 安装之前先确认是否已经存在PostgreSQL rpm -qa | grep postgres# 如果存在࿰…...
《Docker》架构
文章目录 架构模式单机架构应用数据分离架构应用服务器集群架构读写分离/主从分离架构冷热分离架构垂直分库架构微服务架构容器编排架构什么是容器,docker,镜像,k8s 架构模式 单机架构 单机架构其实就是应用服务器和单机服务器都部署在同一…...
从物理机到云原生:全面解析计算虚拟化技术的演进与应用
前言:我的虚拟化技术探索之旅 我最早接触"虚拟机"的概念是从Java开始的——JVM(Java Virtual Machine)让"一次编写,到处运行"成为可能。这个软件层面的虚拟化让我着迷,但直到后来接触VMware和Doc…...
