coding ability 展开第四幕(滑动指针——巩固篇)超详细!!!!

在这里插入图片描述

文章目录

  • 前言
  • 水果成篮
    • 思路
  • 找到字符串中所有字母异位词
    • 思路
  • 串联所有单词的子串
    • 思路
  • 最小覆盖子串
    • 思路
  • 总结

前言

本专栏上一篇博客,带着大家从认识滑动窗口到慢慢熟悉
相信大家对滑动窗口已经有了大概的认识
其实主要就是抓住——一段连续的区间
今天来学习一些滑动窗口进阶的题目
fellow me

水果成篮

在这里插入图片描述

思路

一开始看到这个题目,一段连续的区间,想到了滑动窗口
然后就想着怎么维护窗口,每次更新到新的水果种类就要,开始对left++,然后处理数据
其实是有点麻烦的,但是经过半个多小时的调试,最后还是ac了
思路:每次更新两个种类的水果,x,y,如果下一个水果的种类不相符合,就更新新的x,y
这个时候 right - 1 和 right 所对应的水果就是新的两种,然后就是处理从 left 到 right - 1这段区间
符合条件的情况, 也就是 从right - 1 一直往前走,到与 right - 1 所对应种类不同的水果,然后再更新结果
在反复进窗口,维护窗口,出窗口

代码如下 :

class Solution
{
public:int totalFruit(vector<int>& fruits){int ans = 0;int n = fruits.size();int x = fruits[0], y = fruits[0];if (n == 1)return 1;int left = 0, right = 1;for (; right < n; right++){if (fruits[right] != x && fruits[right] != y)  // 和前面确定的水果种类{y = fruits[right - 1];		//  更新新的水果种类  x = fruits[right];int i = right - 1;if (i != left)  // left  到  right - 1  区间  {while (fruits[i] == y && i > left)  //  i一直靠近left  直到种类不同{i--;}if (i == left && y != fruits[left])  //  更新  left 的指向left++;else if (i != left)left = i + 1;}}ans = max(ans, right - left + 1);//    更新结果}return ans;}
};

后面又想到了一种思路:
就是用哈希来统计种类数量,哈希相对于前面的那种方法还是简单的
就是把两个种类的水果放入哈希表,然后right++ 水果进窗口,如果哈希表的水果种类大于2
就从左侧 left 开始逐步出窗口,直到哈希表种类等于2,然后更新结果

代码如下:

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;}
};

找到字符串中所有字母异位词

在这里插入图片描述

思路

看到又是一段连续的区间,就想到了滑动窗口
这一题 p 的异位词,说白了就是包含了 p 的所有字母,不管先后顺序
想到上一题用哈希优化的爽快,这题好像也可以用哈希来解
把 p 中字符都用哈希统计频次,然后在遍历 s 时,进窗口,维护窗口,出窗口
每次进入窗口,就用哈希统计出现次数,只要没有到达次数上限,就进窗口
如果进入窗口的字符数量大于了 p 的长度,维护窗口从left开始往右开始出窗口
每一次统计进入窗口的数量时,都比较一下 p 的字符个数,如果进入窗口的字符个数等于 p的个数大小相等,就更新结果

代码如下:

class Solution
{
public:vector<int> findAnagrams(string s, string p){vector<int> ret;int hash1[26] = { 0 }; // 统计字符串 p 中每个字符出现的个数for(auto ch : p) hash1[ch - 'a']++;int hash2[26] = { 0 }; // 统计窗口里面的每一个字符出现的个数int m = p.size();for(int left = 0, right = 0, count = 0; right < s.size(); right++){char in = s[right];// 进窗口 + 维护 countif(++hash2[in - 'a'] <= hash1[in - 'a']) count++;if(right - left + 1 > m) // 判断{char out = s[left++];// 出窗口 + 维护 countif(hash2[out - 'a']-- <= hash1[out - 'a']) count--;}// 更新结果if(count == m) ret.push_back(left);}return ret;}
};

下面就上难度了嗷~~~~

串联所有单词的子串

在这里插入图片描述

思路

这个题目看起来很难,其实一点也不简单,看到困难的标签就让人望而生畏
但其实也没有想象的那么难,慢慢抽丝剥茧,其实也能拿下
在这里插入图片描述
看到这里,其实就想到了上一题的那个字母异位词,本题是说所有单词都包含,然后不管顺序
上一题是——所有字母都包含,然后不管顺序,我们不妨试试上一题的思路呢
首先要解决的就是把单词抽象变成字符,我们可以定义一个 string,映射 int 的 哈希表,这个问题就迎刃而解了
下一个问题就是怎么才能知道哪个是单词的开头字母呢??又怎么在 s 中遍历单词然后进窗口呢??
在这里插入图片描述
我又看到了这个条件,雪中送炭,所有单词长度相等,那岂不是起飞了,就让 right 每次遍历 += 单词长度就好了
这些都处理好了,最后一个问题就是,我怎么知道哪个字符是单词的第一个字母,错乱了怎么办,那不是gg
我们只需要在外面套一层for循环,从0到单词的长度,这段区间都做一次滑动窗口就好啦
核心问题都解决了,剩下的就是一些细节处理问题了
话不多说,这些都解决了,开始执行代码:

class Solution 
{
public:vector<int> findSubstring(string s, vector<string>& words) {vector<int> ret;unordered_map<string, int> hash1; // 保存 words 里面所有单词的频次for (auto& c : words)hash1[c]++;int len = words[0].size(), m = words.size();for (int i = 0; i < len; i++) // 执行 len 次{unordered_map<string, int> hash2; // 维护窗口内单词的频次for (int left = i, right = i, count = 0; right + len <= s.size();right += len) {// 进窗口 + 维护 countstring in = s.substr(right, len);hash2[in]++;if (hash1.count(in) && hash2[in] <= hash1[in])count++;// 判断if (right - left + 1 > len * m) {// 出窗口 + 维护 countstring out = s.substr(left, len);if (hash1.count(out) && hash2[out] <= hash1[out])count--;hash2[out]--;left += len;}// 更新结果if (count == m)ret.push_back(left);}}return ret;}
};

其实hard题也是由一个一个小问题糅合起来的,解决核心问题,其实也没有那么难
慢慢啃下来,还是有成就感的 come on

最小覆盖子串

在这里插入图片描述

思路

又又又是一段连续的区间,来吧来吧,滑动窗口,滑动窗口
在这里插入图片描述
这道题不是上一题的恰好涵盖所有字符了,要返回的是最小子串,也就是能包含其他的
但是经过前面题目的磨砺,我感觉好像自己有点门道了
思路:用哈希1统计字符串 t 的每一个字符的频次,还有种类
构造一个新的哈希2,然后遍历 s 字符串,每个字符都统计到新的哈希表
当这个字符的频次和 哈希1中统计的字符频次相等时,种类数++
种类数和哈希1种类数相等时维护窗口,更新结果
大致思路就差不多是这样,来执行代码吧

class Solution 
{
public:string minWindow(string s, string t) {int hash1[128] = {0}; // 统计字符串 t 中每一个字符的频次int kinds = 0;        // 统计有效字符有多少种for (auto ch : t)if (hash1[ch]++ == 0)kinds++;int hash2[128] = {0}; // 统计窗口内每个字符的频次int minlen = INT_MAX, begin = -1;for (int left = 0, right = 0, count = 0; right < s.size(); right++) {char in = s[right];if (++hash2[in] == hash1[in])count++;           // 进窗口 + 维护 countwhile (count == kinds) // 判断条件{if (right - left + 1 < minlen) // 更新结果{minlen = right - left + 1;begin = left;}char out = s[left++];if (hash2[out]-- == hash1[out])count--; // 出窗口 + 维护 count}}if (begin == -1)return "";elsereturn s.substr(begin, minlen);}
};

这个困难也拿下啦,滑动窗口和哈希一起用感觉有点爽,绝佳组合

总结

滑动窗口的核心在于维护一段连续区间,通过哈希表优化统计与比较过程。面对不同问题需灵活调整:
哈希表记录元素频次,快速判断窗口合法性(如水果种类、异位词)
双指针动态伸缩窗口,确保时间复杂度为O(N)
多层循环处理定长元素(如单词串联),覆盖所有起点情况
种类与频次匹配时更新结果,最小子串问题需全局记录最优解
掌握滑动窗口+哈希的组合,能高效解决子串、子数组等连续区间问题,突破Hard瓶颈

今天的内容就到这里啦,不要走开,小编持续更新中~~~~

在这里插入图片描述

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

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

相关文章

“消失的中断“

“消失的中断” 1. 前言 在嵌入式开发过程中&#xff0c;中断必不可少。道友们想必也经常因为中断问题头疼不已&#xff0c;今天来说说一个很常见的问题&#xff0c;“消失的中断”。最近项目在使用第三方MCAL的时候&#xff0c;就遇到了I2C中断丢失的问题&#xff0c;排查起…

阿里云魔笔低代码应用开发平台快速搭建教程

AI低代码&#xff0c;大模型时代应用开发新范式 什么是魔笔 介绍什么是魔笔低代码应用开发平台。 魔笔是一款面向全端&#xff08;Web、H5、全平台小程序、App&#xff09;场景的模型驱动低代码开发平台&#xff0c;提供一站式的应用全生命周期管理&#xff0c;包括可视化开发…

Obsidian Copilot:打造你的专属 AI 笔记助手

Obsidian Copilot作为一款非常受欢迎的Obsidian插件&#xff0c;不仅极大地提升了用户的笔记管理和信息检索效率&#xff0c;还通过其多样化的AI功能为用户带来了前所未有的便捷体验。本文将详细介绍Obsidian Copilot的核心特点、使用方法及个人体验分享。 核心特点 Obsidian…

聊聊 Redis 的一些有趣的特性(上)

聊聊 Redis 的一些有趣的特性&#xff08;上&#xff09; 一、持久化 Redis 是内存数据库&#xff0c;数据全部保存在内存中。如果服务器发生宕机&#xff0c;内存中的数据将会全部丢失。为防止系统崩溃后数据丢失&#xff0c;Redis 提供了持久化功能&#xff0c;可将内存中的…

【结构设计】3D打印创想三维Ender 3 v2

【结构设计】3D打印创想三维Ender 3 v2 文章目录 前言一、Creality Slicer1.2.3打印参数设置二、配件更换1.捆扎绑扎线2.气动接头3D打印机配件插头3.3D打印机配件Ender3pro/V2喷头套件4.读卡器 TF卡5.micro sd卡 三、调平四、参考文章总结 前言 使用工具&#xff1a; 1.创想三…

吴恩达机器学习笔记复盘(五)均方误差函数

只讲了线性回归的代价函数。 均方误差&#xff08;Mean Squared Error, MSE&#xff09; 均方误差&#xff08;MSE&#xff09;基于最小二乘法&#xff0c;通过计算预测值与真实值之间差值的平方的平均值来衡量模型的误差。 原理 假设我们有一组数据集&#xff0c;其中是第…

Vue生命周期_Vue生命周期钩子

一、生命周期介绍 每个 Vue 组件实例在创建时都需要经历一系列的初始化步骤&#xff0c;比如设置好数据侦听&#xff0c;编译模板&#xff0c;挂载实例到 DOM&#xff0c;以及在数据改变时更新 DOM。 在此过程中&#xff0c;它也会运行被称为生命周期钩子的函数&#xff0c;让…

arthas常用命令

文章目录 1. dashboard仪表板2. 通过thread命令来获取到math-game.jar进程的Main Class3. 通过jad来反编译Main Class4. watch监视5. 退出arthas6. 小结 欢迎关注 性能测试和优化 专栏&#xff1a;https://blog.csdn.net/qq_41684621/category_12910565.html 1. dashboard仪表…

c#Winform也可以跨平台了GTK框架GTKSystem.Windows.Forms

一、简介 >> 新版下载&#xff0c;问题求助 QQ群&#xff1a;1011147488 1032313876 236066073&#xff08;满&#xff09; Visual Studio原生开发&#xff0c;无需学习&#xff0c;一次编译&#xff0c;跨平台运行. C#桌面应用程序跨平台&#xff08;windows、linux、…

Vue3 Pinia的getters属性

Pinia的getters属性 定义一个bigSum&#xff0c;值是sum*10 可以写成箭头函数的形式upperSchool中使用了this&#xff0c;不能写成箭头函数的形式

Atcoder ABC397-D 题解

https://atcoder.jp/contests/abc397/tasks/abc397_dhttps://atcoder.jp/contests/abc397/tasks/abc397_d 题目描述&#xff1a; 确定是否存在一对正整数,使得 思路&#xff1a; 首先对方程进行转化 设 即 接下来确定的范围 根据立方差公式 因此&#xff0c;我们可以从到来…

医疗送药机器人“空间拓扑优化+动态算法决策+多级容错控制”三重链式编程技术解析与应用

一、引言 1.1 研究背景与意义 在医疗体系中,高效精准的药品配送是保障医疗服务质量和患者安全的关键环节。随着医疗技术的不断进步和医疗需求的日益增长,传统的人工送药方式逐渐暴露出诸多弊端,如配送效率低下、易受人为因素干扰导致错误率上升、人力成本高昂等。特别是在…

Redis实现高并发排行榜的功能

生活中排行榜是常见的功能&#xff0c;如游戏的排行榜&#xff0c;销售额的排行榜等等&#xff0c;排行榜不仅可以让用户有更多的激情参与到活动中来&#xff0c;而且可以更好的留存住用户&#xff0c;如下所示的拉新排行榜&#xff1a; 排行榜是一个常见的业务需求&#xff0…

数字孪生像魔镜,映照出无限可能的未来

在当今科技飞速发展的时代&#xff0c;数字孪生作为一项极具潜力的前沿技术&#xff0c;正逐渐崭露头角&#xff0c;成为众多领域关注的焦点。它犹如一面神奇的魔镜&#xff0c;以数字化的方式精准映照出现实世界中的各种实体与系统&#xff0c;为我们开启了一扇通往无限可能未…

每日一题---

深拷贝和浅拷贝的区别是什么&#xff1f; null 浅拷贝是指只复制对象本身和其内部的值类型字段&#xff0c;但不会复制对象内部的引用类型字段。换句话说&#xff0c;浅拷贝只是创建一个新的对象&#xff0c;然后将原对象的字段值复制到新对象中&#xff0c;但如果原对象内部有…

Chrome 扩展开发 API实战:Sessions (六)

1. 引言 chrome.sessions 是 Chrome 扩展开发者工具的一部分&#xff0c;提供了对最近关闭的标签页和窗口的访问&#xff0c;以及对会话恢复功能的支持。现代浏览器的一个显著特点是为用户提供更多的便利性&#xff0c;比如快速恢复意外关闭的页面。通过 chrome.sessions API&…

Spring Boot对接twilio发送邮件信息

要在Spring Boot应用程序中对接Twilio发送邮件信息&#xff0c;您可以使用Twilio的SendGrid API。以下是一个简单的步骤指南&#xff0c;帮助您完成这一过程&#xff1a; 1. 创建Twilio账户并获取API密钥 注册一个Twilio账户&#xff08;如果您还没有的话&#xff09;。在Twi…

学习15天:pytest

1、.pytest强大的插件 pytest-html(生成html格式的自动化测试报告) pytest-xdist测试用例分布式执行。多CPU分发。 pytest-ordering 用于改变测试用例的执行顺序 pytest-rerunfailures用例失败后重跑 allure-pytest 用于生成美观的测试报告。 2、规则&#xff1a; 模块…

Springboot+mybatis实现增删改查操作

继续写一下删除操作&#xff0c;删除有些不一样&#xff0c;首先在controller里面&#xff0c;我们需要改一下路由&#xff0c;我们后面要写/{id}传入路径参数&#xff0c;用PathVariable注解绑定id&#xff0c;剩下的都一样&#xff0c;传入id&#xff0c;然后写service和mapp…

Visual Studio里的调试(debugging)功能介绍

参考 1- Introduction to Debugging | Basic Visual Studio Debugging&#xff08;这是一位印度博主视频&#xff0c;我下面做到笔记也主要参考她的视频&#xff0c;但不得不说口音太重了&#xff0c;一股咖喱味&#xff09; 目录 个人对调试浅显的认识和对调试的介绍逐行调…