滑动窗口代码模板
代码模板:
//滑动窗口伪代码
class Solution {
public:int minWindow(string s) {// 同方向移动,起始的时候,都位于 0,表示我们定义搜索区间为 [left, right) ,此时区间为空区间int left = 0;int right = 0;while(right < Slen){//每一次循环的开始,都一定不满足条件//(因为上一次循环是从满足条件跳出while的)// 这里对状态做修改,好让程序在后面检测到满足条件right++; //右移right,实际上,这一句也可以写在外层while的最后一句while(满足条件){ // 对状态做修改,好让程序在后面检测到不满足条件left++; //右移left}//记录当前最接近结果的值}return maxlen;}
};
例题1:leecode第3题:无重复字符的最长子串
给定一个字符串 s ,请你找出其中不含有重复字符的 最长
子串
的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
提示:
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成
解答:
class Solution {
public:int lengthOfLongestSubstring(string s) {int len = s.size();if(len < 2){return len;}int *freq = new int[128];for(int i = 0; i < 128; i++){freq[i] = 0;}int maxlen = 1;//维护一个变量用于记录最长字符串的长度int left = 0, right = 0;//循环不变量 [left, right)无重复字符串while(right < len){freq[s[right]]++; // 对状态做修改,好让程序在后面检测到满足条件:[left, right)出现重复元素right++;while(freq[s[right-1]] == 2){//满足条件:[left, right)出现重复元素freq[s[left]]--;left++; }maxlen = maxlen < (right - left) ? (right - left) : maxlen;//记录当前最接近结果的值}return maxlen;}
};
例题2:lecoode第76题:最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 “” 。
注意:
对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串,我们保证它是唯一的答案。
示例 1:
输入:s = "ADOBECODEBANC", t = "ABC"
输出:"BANC"
解释:最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
示例 2:
输入:s = "a", t = "a"
输出:"a"
解释:整个字符串 s 是最小覆盖子串。
示例 3:
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中,
因此没有符合条件的子字符串,返回空字符串。
提示:
m == s.length
n == t.length
1 <= m, n <= 105
s 和 t 由英文字母组成
进阶:你能设计一个在 o(m+n) 时间内解决此问题的算法吗?
解答:
class Solution {
public:string minWindow(string s, string t) {int s_len = s.size();int t_len = t.size();int count = 0; //记录t包含的字母个数vector<int> MinWindow(128, 0); //记录滑动窗口各个字母出现的次数vector<int> CharArray(128, 0); //记录t包含各个字母出现的次数//记录t每个字母出现的次数for(int i = 0; i < t_len; ++i){++CharArray[t[i]];}//记录t有多少个字母for(int i = 0; i < 128; ++i){if(CharArray[i] > 0){++count;}}int left = 0; //滑动窗口的左边int right = 0; //滑动窗口的右边int m_left = 0; //记录最小子串在s的起始位置int minLen = s_len + 1; //记录最小子串的长度int sameNumber = 0; //记录s中与t相同的字母的个数while(right < s_len){char rc = s[right];//这个字母在t中出现if(CharArray[rc] > 0){//将这个字母加入到记录滑动窗口的数组中++MinWindow[rc];//此时这个字母在s出现的次数等于在t出现的次数,即s中这个字母满足覆盖t子串的要求if(MinWindow[rc] == CharArray[rc]){++sameNumber;}}++right;//当s中满足t中所有出现的字母要求while(sameNumber == count){//维护当前最小字符串的起始和偏移if(minLen > right - left){minLen = right - left;m_left = left;}char lc = s[left];//对滑动窗口将要做边界右移会造成的状态进行统计if(CharArray[lc] > 0){--MinWindow[lc];if(MinWindow[lc] < CharArray[lc]){--sameNumber;}}//滑动窗口左边界右移++left;}}//如果没进入sameNumber == count循环,证明s是不满足包含t的条件,则返回空字符串return minLen == 1 + s_len ? "" : s.substr(m_left, minLen);}
};
例题3:leecode lcr第8题:长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。
示例 1:
输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2:
输入:target = 4, nums = [1,4,4]
输出:1
示例 3:
输入:target = 11, nums = [1,1,1,1,1,1,1,1]
输出:0
提示:
1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105
解答:
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int len = nums.size();//先判断特殊情况,如果数组总和都小于targer,则返回0(即示例3的情况)int sum = 0;for(int i = 0; i < len; i++){sum += nums[i];}if(sum < target) return 0;int WindowSum = 0; //记录当前窗口的元素和int min_len = len; //维护一个最小长度int left = 0, right = 0;while(right < len){WindowSum += nums[right];right++;while(WindowSum >= target){min_len = (min_len < right - left) ? min_len : (right - left);WindowSum -= nums[left];left++;}}return min_len;}
};
例题4:leecode 438. 找到字符串中所有字母异位词:(固定窗口大小的滑动窗口问题)
给定两个字符串 s 和 p,找到 s 中所有 p 的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串(包括相同的字符串)。
示例 1:
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
示例 2:
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
提示:
1 <= s.length, p.length <= 3 * 104
s 和 p 仅包含小写字母
解答:
class Solution {
public:vector<int> findAnagrams(string s, string p) {int s_len = s.size();int p_len = p.size(); vector<int> res;//记录结果使用if(s_len < p_len) return res;vector<int> freq_p(26, 0);vector<int> window_freq(26, 0);//统计p的频数for(int i = 0; i < p_len; i++){freq_p[p[i] - 'a']++;}//窗口的长度固定为p的长度,并统计窗口在最初始的频数int left = 0, right = p_len - 1;for(int i = 0; i < p_len; i++){window_freq[s[i] - 'a']++;}while(right < s_len - 1 ){int isEq = IsArrEq(window_freq, freq_p);if(isEq){res.push_back(left);}//移动窗口,并统计移动后的频数window_freq[s[left] - 'a']--;left++;window_freq[s[right + 1] - 'a']++;right++;}//跳出循环后,还要单独判断一下移动到s最右侧的情况int isEq = IsArrEq(window_freq, freq_p);if(isEq){res.push_back(left);}return res;}
//此函数用于判断两个频数数组是否相等int IsArrEq(vector<int> arr1, vector<int>arr2){for(int i = 0; i < 26; i++){if(arr1[i] != arr2[i])return 0;}return 1;}
};
相关文章:
滑动窗口代码模板
代码模板: //滑动窗口伪代码 class Solution { public:int minWindow(string s) {// 同方向移动,起始的时候,都位于 0,表示我们定义搜索区间为 [left, right) ,此时区间为空区间int left 0;int right 0;while(right…...
SpringBoot实现邮箱验证
目录 1、开启邮箱IMAP/SMTP服务,获取授权码 2、相关代码 1、使用配置Redis(用于存储验证码,具有时效性) 2、邮箱依赖和hutool(用于随机生成验证码) 3、配置Redis和邮箱信息 4、开启Redis服务 5、编写发送…...
Mac安装Docker提示Another application changed your Desktop configuration解决方案
1. 问题描述 Mac安装Docker后,提示Another application changed your Desktop configuration,Re-apply configurations无效 2. 解决方案 在终端执行下述命令即可解决: sudo ln -sf /Applications/Docker.app/Contents/Resources/bin/docke…...
5分钟安装docker和docker compose环境
5分钟安装docker和docker compose环境 5分钟安装docker和docker compose环境环境介绍卸载docker环境安装docker安装docker compose 5分钟安装docker和docker compose环境 你好! 这是你第一次使用 Markdown编辑器 所展示的欢迎页。如果你想学习如何使用Markdown编辑…...
leetcode热题100.跳跃游戏2
Problem: 45. 跳跃游戏 II 文章目录 题目思路复杂度Code 题目 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i j] 处: …...
【前端】CSS(引入方式+选择器+常用元素属性+盒模型+弹性布局)
文章目录 CSS一、什么是CSS二、语法规范三、引入方式1.内部样式表2.行内样式表3.外部样式 四、选择器1.选择器的种类1.基础选择器:单个选择器构成的1.标签选择器2.类选择器3.id 选择器4.通配符选择器 2.复合选择器1.后代选择器2.子选择器3.并集选择器4.伪类选择器 五…...
迷茫下是自我提升
长夜漫漫,无心睡眠。心中所想,心中所感,忧愁当前,就执笔而下,写下这篇文章。 回忆过往 回想当初为啥学前端,走前端这条路,学校要求嘛,兴趣爱好嘛,还是为了钱。 时间带着…...
用vscode仿制小米官网
html内容: <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>Document</title><link rel&quo…...
【Java+Springboot】------ 通过JDBC+GetMapping方法进行数据select查询、多种方式传参、最简单的基本示例!
一、JDBC如何使用、PostGresql数据库 1、在pom.xml 先引用jdbc组件。 <!--jdbc--><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-jdbc</artifactId></dependency> 2、在pom.xml 再引用p…...
基于单片机光伏太阳能跟踪系统设计
**单片机设计介绍,基于单片机光伏太阳能跟踪系统设计 文章目录 一 概要二、功能设计三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机光伏太阳能跟踪系统的设计,旨在通过单片机技术实现对光伏太阳能设备的自动跟踪,以提高太阳…...
Stable Diffusion 本地化部署
一、前言 最近在家背八股文背诵得快吐了,烦闷的时候,看到使用 AI 进行作图,可以使用本地话部署。刚好自己家里的电脑,之前买来玩暗黑4,配置相对来说来可以,就拿来试试。 此篇是按照 Github 上的 stable-d…...
C++ Algorithm 常用算法
C <algorithm> 头文件是标准库中提供的一系列算法,用于操作范围(range)内的元素。这些算法可以用于数组、容器如vector和list,以及其他满足相应迭代器要求的数据结构。以下是一些常用的C <algorithm> 中的算法及其使用…...
线程安全--深入探究线程等待机制和死锁问题
꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好,我是xiaoxie.希望你看完之后,有不足之处请多多谅解,让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如需转…...
量子计算获重大突破!微软和Quantinuum将量子计算错误率降低800倍,网友:AI算力的希望
量子计算迎来新突破。 近日,微软和量子计算公司Quantinuum宣布:发现了一种新的量子计算系统,可以将传统量子计算的错误率下降800倍,这让高性能量子计算机走进现实更近了一步。 自生成式AI爆发以来,算力是AI发展面临的…...
WordPress 6.5 “里贾纳”已经发布
WordPress 6.5 “里贾纳”已经发布,其灵感来自著名爵士小提琴家Regina Carter的多才多艺。雷吉娜是一位屡获殊荣的艺术家和著名的爵士乐教育家,以超越流派而闻名,她在古典音乐方面的技术基础和对爵士乐的深刻理解为她赢得了大胆超越小提琴所能…...
甲方安全建设之日志采集实操干货
前言 没有永远的安全,如何在被攻击的情况下,快速响应和快速溯源分析攻击动作是个重要的话题。想要分析攻击者做了什么、怎么攻击进来的、还攻击了谁,那么日志是必不可少的一项,因此我们需要尽可能采集多的日志来进行分析攻击者的…...
dm8 开启归档模式
dm8 开启归档模式 1 命令行 [dmdbatest1 dm8]$ disql sysdba/Dameng123localhost:5237服务器[localhost:5237]:处于普通打开状态 登录使用时间 : 3.198(ms) disql V8 SQL> select name,status$,arch_mode from v$database;行号 NAME STATUS$ ARCH_MODE ----------…...
“AI复活”背后的数字永生:被期待成为下一个电商,培育市场认知和用户心智还需时间
“AI复活”背后的数字永生:被期待成为下一个电商,培育市场认知和用户心智还需时间© 由 九派新闻 提供 数字永生,还是电子宠物?过去一个月,因包小柏用AI技术让爱女在数字世界“复活”一事,《流浪地球2…...
基于单片机钢琴电子节拍器系统设计
**单片机设计介绍,基于单片机钢琴电子节拍器系统设计 文章目录 一 概要二、功能设计三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机钢琴电子节拍器系统设计是一个综合性的项目,它结合了单片机编程、音频处理、用户界面设计等多个领域的…...
我的创作纪念日(year Ⅱ)
大家好,我是Kamen Black 君,今天我与大家简单分享一下我两年来在CSDN的创作历程。 print("祝大家每天快乐,love and peace!") 机缘 当初写博客是为了记录一些自己大学中做比赛的心得,没想到自己能走到这一步…...
应急响应实战笔记05Linux实战篇(1)
第1篇:SSH暴力破解 0x00 前言 SSH 是目前较可靠,专为远程登录会话和其他网络服务提供安全性的协议,主要用于给远程登录会话数据进行加密,保证数据传输的安全。SSH口令长度太短或者复杂度不够,如仅包含数字&#x…...
重装系统之后,电脑连网卡都没反应怎么办?
前言 有些电脑比较奇葩,安装完成之后会出现网卡连驱动都没有,这时候要安装电脑驱动可是真的烦躁。怎么下手呢? 如果确定电脑的网卡型号还好,直接找个电脑下载个对应的网卡驱动,用U盘复制过去就能安装。 但如果不知道…...
【三十五】【算法分析与设计】综合练习(2),22。 括号生成,77。 组合,494。 目标和,模拟树递归,临时变量自动维护树定义,递归回溯,非树结构模拟树
22. 括号生成 数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。 示例 1: 输入:n 3 输出:["((())࿰…...
QT智能指针
一.概述 Qt智能指针是一种能够在不需要手动管理内存的情况下,自动释放资源的指针。它们是C11的std::shared_ptr的一种扩展,可以用于管理Qt对象,尤其是那些不是QObject的对象。 使用智能指针可以避免内存泄露和悬垂指针等问题,同时…...
C++笔记之pkg-config详解,以及g++、gcc编译时使用pkg-config
C++笔记之pkg-config详解,以及g++、gcc编译时使用pkg-config —— 2024-04-05 code review 文章目录 C++笔记之pkg-config详解,以及g++、gcc编译时使用pkg-config1.pkg-config详解`pkg-config` 的基本用法在 `g++`/`gcc` 编译时使用 `pkg-config`注意事项2.示例C++,普通编译…...
[Apple Vision Pro]开源项目 Beautiful Things App Template
1. 技术框架概述: - Beautiful Things App Template是一个为visionOS设计的免费开源软件(FOSS),用于展示3D模型画廊。 2. 定位: - 该模板作为Beautiful Things网站的延伸,旨在为Apple Vision Pro用户…...
Qt Remote Objects (QtRO) 笔记
简介 Qt Remote Objects (QtRO) 是 Qt 的一个进程间通信模块。 术语 Source 是指提供服务或提供功能供其他程序使用的对象,是 RPC 中的被调用端。 Replica 是指 Source 对象的代理对象,用于 RPC 中的调用端,对 Replica 的调用请求将被转发…...
Unity类银河恶魔城学习记录12-6.5 p128.5 Create item by Craft源代码
此章节在原视频缺失,此过程为根据源代码推断而来,并非原视频步骤 Alex教程每一P的教程原代码加上我自己的理解初步理解写的注释,可供学习Alex教程的人参考 此代码仅为较上一P有所改变的代码 【Unity教程】从0编程制作类银河恶魔城游戏_哔哩…...
UE4_如果快速做出毛玻璃效果_假景深
UE4_如果快速做出毛玻璃效果_假景深 2022-08-20 15:02 一个SpiralBlur-SceneTexture材质节点完成效果,启用半透明材质通过修改BlurAmount数值大小调整效果spiralBlur-SceneTexture custom节点,HLSL语言float3 CurColor 0;float2 BaseUV MaterialFloa…...
c# wpf LiveCharts 绑定 简单试验
1.概要 c# wpf LiveCharts 绑定 简单试验 2.代码 <Window x:Class"WpfApp3.Window2"xmlns"http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x"http://schemas.microsoft.com/winfx/2006/xaml"xmlns:d"http://schem…...
外包做的网站 需要要源代码吗/天门seo
文/辛东方移动互联网时代,人们利用互联网和和便捷的移动终端设备宣传和销售自己的产品。而有些人则利用互联网时代所创造的便捷机会到处招摇撞骗,甚至走上违法犯罪道路。2015年2月9日,江苏省泰州市中级人民法院,对被告人贾某销售假…...
哪个网站专门做快餐车/南宁seo关键词排名
1.登录was控制台https://172.16.87.221:9043/ibm/console/unsecureLogon.jsp服务器--服务器类型--Java 和进程管理---进程定义---Java 虚拟机通用JVM参数:-Djavax.management.builder.initial -Dcom.sun.management.jmxremote 2.修改/opt/IBM/WebSphere/AppServer/java/jre/lib…...
网站建设可以自己建设服务器吗/企业模板建站
echo echo [-neE] [arg …],输出arg,多个arg由空格分隔,以换行符结束。除非发生写错误,否则返回状态为0。-n选项,不输出最后换行符。-e选项,启用反斜杠转义。-E选项,禁用反斜杠转义,…...
重庆建设网站首页/sem运营有出路吗
微软近期推出了首款 ChatGPT 版搜索引擎,今天带大家一起来看一下。 一夜之间,全球最大的科技公司仿佛都回到了自己年轻时的样子。 在谷歌宣布「实验性对话式人工智能服务」Bard 之后仅 24 小时,北京时间 2 月 8 日凌晨两点,微软发…...
简单的网站怎样做/营销技巧和营销方法视频
1 简介:JDK提供的java.util.Properties类继承自Hashtable类并且实现了Map接口,是使用一种键值对的形式来保存属性集,其中键和值都是字符串类型。java.util.Properties类提供了getProperty()和setProperty()方法来操作属性文件,同时…...
投票网站如何做/最佳bt磁力猫
http://adamsitnik.com/Disassembly-Diagnoser/ http://mattwarren.org/2018/01/22/Resources-for-Learning-about-.NET-Internals/...