leetcode:滑动窗口

目录

1.定长滑动窗口

1.1 几乎唯一子数组的最大和(使用map来计数)

1.2 长度为k子数组中的最大和

2.不定长滑动窗口

2.1 最多k个重复元素的最长子数组

2.2 绝对差不超过限制的最长连续子数组(multiset)

2.3 将x减到0的最小操作数(正难则反 逆向思维)

2.4 统计最大元素出现至少k次的子数组

2.5 乘积小于k的子数组


1.定长滑动窗口

1.1 几乎唯一子数组的最大和(使用map来计数)

class Solution {
public:long long maxSum(vector<int>& nums, int m, int k) {long long ans = 0, sum = 0;unordered_map<int, int>cnt; //如何把重复的数字算成一个数字,就要用到数组来进行计数了,重复的数字对应的值大于1for (int i = 0; i < k - 1; i++) //先求前k-1个数{sum += nums[i];cnt[nums[i]]++;}for (int i = k - 1; i < nums.size(); i++) //进去一个出来一个,满足k个数{sum += nums[i];cnt[nums[i]]++;if (cnt.size() >= m) //判断是否有m个不相同的数ans = max(ans, sum);int out = nums[i - k + 1];sum -= out;if (--cnt[out] == 0) //如果只出现1次,可以直接删除cnt.erase(out);}return ans;}
};

      这道题让我们求最大的问题,而且是连续非空的子数组,很容易想到滑动窗口,但滑动窗口有定长和不定长两种,题中说长度为k,说明是定长的,要求长度为k的几乎唯一子数组的最大和,我们可以先求前k-1个数,这样之后进来一个出去一个,始终是k个数,题目要求该子数组至少有m个不相同的数,我们怎么记录是否有m个不相同的数呢?我们可以用map来记录有几个不相同的数,同时记录每个数字出现了几次,如果某个子数组有m个不相同的数,就更新答案,之后就要出去一个数,如果出去的这个数只出现了1次,就要直接从map中删除。最后返回答案

1.2 长度为k子数组中的最大和

class Solution {
public:long long maximumSubarraySum(vector<int>& nums, int k) {unordered_map<int, int> mp;long long res = 0, sum = 0;for (int i = 0; i < k - 1; i++) {sum += nums[i];mp[nums[i]]++;}for (int i = k - 1; i < nums.size(); i++) {sum += nums[i];mp[nums[i]]++;if (mp.size() == k ) res =max(res,sum);//这个已经去重了,只要当mp的大小等于k时,才会更新res的大小,否则说明有重复数字,不更新int x = nums[i - k + 1];if (--mp[x] == 0) mp.erase(x);//及时清除为0的数字sum -= x;}return res;}
};

      这道题也是定长滑动窗口,要求子数组长度为k,且元素各不相同,和上一道题很相似,也要用map,值得注意的是什么时候我们更新答案,只有当map中的元素个数等于k时,说明子数组长度为k,且元素各不相同,这时候更新答案,其他都是不断滑动的过程。

2.不定长滑动窗口

2.1 最多k个重复元素的最长子数组

class Solution {
public:int maxSubarrayLength(vector<int>& nums, int k) {unordered_map<int,int>cnt;int ans=0,l=0;for(int r=0;r<nums.size();r++){cnt[nums[r]]++;while(cnt[nums[r]]>k)//如果有元素的出现频率大于k,就要不断左移左指针,直到这个元素的出现频率小于等于k,如果这个元素cnt[nums[l++]]--;ans=max(ans,r-l+1);}return ans;}
};

     这个没有规定长度,要求满足条件的最长子数组,很明显是不定长滑动窗口的问题。最多k个重复元素说明我们要记录元素出现了几次,一旦超过了k次,我们就要开始滑动,直到子数组没有一个元素的出现频率大于k,否则不断更新答案。

2.2 绝对差不超过限制的最长连续子数组(multiset)

class Solution {
public:int longestSubarray(vector<int>& nums, int limit) {multiset<int>st;//关键在于找每个区间的最大值和最小值,如果遍历寻找,就会超时,所以要找到一个合适的数据结结构//我们知道set/multiset/map是有序的,set会去重,所以我们使用multisetint l=0;int res=0;for(int r=0;r<nums.size();r++){st.insert(nums[r]);while(*st.rbegin()-*st.begin()>limit){st.erase(st.find(nums[l]));l++;}res=max(res,r-l+1);}return res;}
};

      这道题的关键在于求每个区间的最大值和最小值,首先我们要把元素放到multiset中,它不仅不会去重,而且是有序的,改变顺序并不影响答案,这样我们使用两个迭代器rbegin()、begin()分别求逆序第一个元素和正序第一个元素,两者之差就是绝对差,如果大于限制,我们就不断滑动窗口,直到绝对值小于等于限制,更新答案。

2.3 将x减到0的最小操作数(正难则反 逆向思维)

class Solution {
public:int minOperations(vector<int> &nums, int x) {   //正难则反 逆向思维int target = accumulate(nums.begin(), nums.end(), 0) - x;if (target < 0) return -1;int ans = -1, l = 0, sum = 0, n = nums.size();for (int r = 0; r < n; r++) {sum += nums[r];while (sum > target) sum -= nums[l++]; if (sum == target) ans = max(ans, r - l + 1);}return ans < 0 ? -1 : n - ans;}
};

      这道题借用灵神的思路,正难则反,逆向思维,我们如果维护两个窗口的和,使得和等于x肯定是很麻烦的,那不如我们只维护一个窗口,这个窗口的和要等于整数数组nums的和sum-x,这样只用维护一个区间,不得不说,这个思维太帅了。accumulate函数是用来求某个区间元素的和,0为初始值

2.4 统计最大元素出现至少k次的子数组

class Solution {
public:long long countSubarrays(vector<int>& nums, int k) {long long ans=0;int mx=*max_element(nums.begin(),nums.end());int cnt=0,left=0;        for(auto x:nums){if(x==mx)cnt++;while(cnt==k){if(nums[left]==mx){cnt--;}left++;}ans+=left;}return ans;}
};

      这道题我们首先用max_element函数找出数组最大值,然后就对最大值出现的次数进行计数,如果子数组中最大值出现的次数等于k,那么我们就要滑动,寻找下一个满足条件的子数组,如果左端点对应的值等于最大值,cnt--,左端点向右移动,直到cnt!=k,此时更新答案+left,为什么要加left,因为left是cnt==k进入循环向右移动,left++,直到cnt!=k,退出循环得到了,之前的子数组全部满足要求,所以直接加left。

2.5 乘积小于k的子数组

class Solution {
public:int numSubarrayProductLessThanK(vector<int>& nums, int k) {if(k<=1)return 0;int ans=0,mul=1,l=0;for(int r=0;r<nums.size();r++){mul*=nums[r];while(mul>=k){mul/=nums[l];l++;}ans+=r-l+1;}return ans;}
};

     这道题和上一道题很类似,如果[l,r]区间内子数组的乘积小于k,那么[l+1,r],[l+2,r]...[r,r]全部小于k,个数为r-l+1,更新答案每次加上r-l+1即可。

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

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

相关文章

Developer Tools for Game Creator 1

插件包含: 持久世界时间管理系统 单击以生成对象或预设 游戏内调试控制台 游戏内事件控制台 控制台管理控制 命令模板脚本 游戏内屏幕截图 低分辨率和高分辨率图像 缩略图生成 移动支持 使用Game Creator Action或拖放来激活和控制组件,无需编码。 通过此资产,您可以获得: …

Android 15即将到来,或将推出5大新功能特性

Android15 OneUI电池优化 三星最近完成了对其所有设备的稳定版 One UI 6.0 更新的推出&#xff0c;引起了用户的极大兴奋。据新出现的互联网统计数据显示&#xff0c;即将发布的基于 Android 15 的 One UI 7 将通过优化电池和功耗来重新定义用户体验&#xff0c;这是一项具有突…

React之自定义路由组件

开篇 react router功能很强大&#xff0c;可以根据路径配置对应容器组件。做到组件的局部刷新&#xff0c;接下来我会基于react实现一个简单的路由组件。 代码 自定义路由组件 import {useEffect, useState} from "react"; import React from react // 路由配置 e…

【C++】C++11中的常见语法(上)

C11 一、C11简介二、统一的列表初始化1.&#xff5b;&#xff5d;初始化2. std::initializer_list 三、声明1. auto2. decltype3. nullptr 四、右值引用和移动语义1. 左值引用和右值引用2. 左值引用与右值引用比较3. 右值引用使用场景和意义4. 右值引用引用左值及其一些更深入的…

Python知识点(史上最全)

Python期末考试知识点&#xff08;史上最全&#xff09; python简介 Python是一种解释型语言 Python使用缩进对齐组织代码执行&#xff0c;所以没有缩进的代码&#xff0c;都会在载入时自动执行 数据类型&#xff1a;整形 int 无限大 浮点型 float…

概率论与数理统计-第6章 参数估计

6.1 点估计问题概述 一、点估计的概念 二、评价估计量的标准 无偏性 定义1&#xff1a;设^ θ(X1,…,Xn)是未知参数θ的估计量&#xff0c;若E(^ θ)θ,则称^θ为θ的无偏估计量定理1&#xff1a;设X1,…,Xn,为取自总体X的样本&#xff0c;总体X的均值为μ&#xff0c;方差为…

快速打通 Vue 3(四):标签的 ref 属性与 Vue3 生命周期

很激动进入了 Vue 3 的学习&#xff0c;作为一个已经上线了三年多的框架&#xff0c;很多项目都开始使用 Vue 3 来编写了 这一组文章主要聚焦于 Vue 3 的新技术和新特性 如果想要学习基础的 Vue 语法可以看我专栏中的其他博客 Vue&#xff08;一&#xff09;&#xff1a;Vue 入…

centos 8.0 安装sysbench 1.0.17

序号步骤说明执行命令执行结果备注1 下载并解压sysbench-1.0.17.zip sysbench-1.0.17.zip2安装依赖文件 yum install automake libtool -y yum install /usr/include/libpq-fe.h 3安装sysbench cd sysbench-1.0.17 ./autogen.sh ./configure \ --prefix/sysbench \ --with-pgsq…

【Docker】Linux中Docker技术入门与实战及实用的常规命令

目录 一、引言 1. 说明&#xff1a; 2. Linux介绍 3. Docker简介 二、Docker三要素 1. 镜像&#xff08;Image&#xff09; 2. 容器&#xff08;Container&#xff09; 3. 仓库&#xff08;Repository&#xff09; 三、实现案例 1. 创建 2. 设置镜像 3. 开启设置 …

MidTool的AIGC与NFT的结合-艺术创作和版权保护的革新

在数字艺术和区块链技术的交汇点上&#xff0c;NFT&#xff08;非同质化代币&#xff09;正以其独特的方式重塑艺术品的收藏与交易。将MidTool&#xff08;https://www.aimidtool.com/&#xff09;的AIGC&#xff08;人工智能生成内容&#xff09;创作的图片转为NFT&#xff0c…

Windows启动MongoDB服务报错(错误 1053:服务没有及时响应启动或控制请求)

问题描述&#xff1a;修改MongoDB服务bin目录下的mongod.cfg&#xff0c;然后在任务管理器找到MongoDB服务-->右键-->点击【开始】&#xff0c;启动失败无提示&#xff1a; 右键点击任务管理器的MongoDB服务-->点击【打开服务】&#xff0c;跳转到服务页面-->找到M…

云服务器租用价格表,阿里云腾讯云华为云2024年优惠对比

作为多年站长使市面上大多数的云厂商的云服务器都使用过&#xff0c;很多特价云服务器都是新用户专享的&#xff0c;本文有老用户特价云服务器&#xff0c;阿腾云atengyun.com有多个网站、小程序等&#xff0c;国内头部云厂商阿里云、腾讯云、华为云、UCloud、京东云都有用过&a…

2024--Django平台开发-基础信息(一)

一、前置知识点 - Python环境搭建 (Python解释器、Pycharm、环境变量等) - 基础语法(条件、循环、输入输出、编码等) - 数据类型(整型、布尔型、字符串、列表、字典、元组、集合等) - 函数(文件操作、返回值、参数、作用域等) - 面向对象 (类、对象、封装、继承、多态等)包和模…

java基础之异常练习题

异常 1.Java 中所有的错误/异常都继承自 Throwable类&#xff1b;在该类的子类中&#xff0c; Error 类表示严重的底层错误&#xff0c; 对于这类错误一般处理的方式是 直接报告并终止程序 &#xff1b; Exception 类表示异常。 2.查阅API&#xff0c;完成以下填空&#xff1a;…

大数据-hive函数与mysql函数的辨析及练习-将多行聚合成一行

目录 1. &#x1f959;collect_list: 聚合-不去重 2. &#x1f959;collect_set(col): 聚合-去重 3. &#x1f959;mysql的聚合函数-group_concat 4. leetcode练习题 1. &#x1f959;collect_list: 聚合-不去重 将组内的元素收集成数组 不会去重 2. &#x1f959;collec…

unity中0GC优化方案《zstring》

文章目录 序言简介GC带来的问题性能瓶颈玩家体验受损 使用方式 序言 游戏开发秉承遇到好东西要分享&#xff0c;下面介绍zstring&#xff0c;感谢作者开源无私奉献 源码地址&#xff1a;https://github.com/871041532/zstring 简介 GC带来的问题 性能瓶颈 GC暂停主线程执行…

C++内存小练习

使用数据文件中的一组地震检波器测量值确定可能的地震事件的位置 程序的输入是名为map.txt的数据文件和用于计算短时间能量和长时间能量的 取样值的数目。输出是给出关于潜在的地震事件次数的报告 #include <iostream> #include <fstream>using namespace std;//定…

【Kafka-3.x-教程】-【三】Kafka-Broker、Kafka-Kraft

【Kafka-3.x-教程】专栏&#xff1a; 【Kafka-3.x-教程】-【一】Kafka 概述、Kafka 快速入门 【Kafka-3.x-教程】-【二】Kafka-生产者-Producer 【Kafka-3.x-教程】-【三】Kafka-Broker、Kafka-Kraft 【Kafka-3.x-教程】-【四】Kafka-消费者-Consumer 【Kafka-3.x-教程】-【五…

Mongodb使用指定索引删除数据

回顾Mongodb删除语法 db.collection.deleteMany(<filter>,{writeConcern: <document>,collation: <document>,hint: <document|string>} ) 删除语法中&#xff0c;除了指定过滤器外&#xff0c;还可以指定写入策略&#xff0c;字符序和使用的索引。 …

SQL语句where、group by 等关键词的顺序

聚合函数的结果作为筛选&#xff0c;不能用where&#xff0c;要用having; 语法顺序是&#xff1a;where&#xff0c;group by, having, order by, limit, 顺序不可以换否则会报错。 参考&#xff1a;SQL基础----select、where、order by 、limit&#xff08;mysql&#xff09;…