【算法一周目】滑动窗口(2)
目录
水果成篮
解题思路
代码实现
找到字符串中所有字母异位词
解题思路
代码实现
串联所有单词的子串
解题思路
代码实现
最小覆盖子串
解题思路
代码实现
水果成篮
题目链接:904. 水果成篮
题目描述:
你正在探访一家农场,农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示,其中 fruits[i] 是第 i 棵树上的水果种类。你想要尽可能多地收集水果,但是有一些规则:
- 你有两个篮子,每个篮子只能装一种类型的水果,篮子的容量无限制。
- 你可以选择任意一棵树开始采摘,但必须从这棵树开始依次向右采摘每棵树上的水果。
- 一旦遇到某棵树上的水果不符合篮子中的水果种类,你必须停止采摘。
返回你能采摘的最多的水果数量。
解题思路
解法:滑动窗口+哈希
根据题目要求,所求问题其实就是找一段最多只含两个不同元素的最长子区间,我们使用滑动窗口+哈希解决。
有一点值得注意,fruits[i] 是第 i 棵树上的水果种类,不是种类数。
具体过程如下:
- 1.初始化哈希表 hash,左右指针 left 和 right,记录结果的变量 ret。
- 2.right 向右遍历数组,将 right 位置的水果加入哈希表,统计频次。
- 如果哈希表的大小超过2,让left++并同时更新哈希表,直至哈希表的大小不超过2。
- 3.更新结果 ret。
- 4重复上述过程,直到 right 遍历完数组。
代码实现
1.使用unordered_map作为hash表
class Solution {
public:int totalFruit(vector<int>& fruits) {// 统计滑动窗口内水果的种类和数量unordered_map<int, int> hash;int n = fruits.size(), ret = 0;for(int left = 0, right = 0; right < n; right++){//进窗口,将水果加入hash表hash[fruits[right]]++;//若水果种类超过2,收缩窗口直到种类不超过2while(hash.size() > 2){hash[fruits[left]]--;if(hash[fruits[left]] == 0) hash.erase(fruits[left]);left++;}//更新结果ret = max(ret, right - left + 1);}return ret;}
};
2.使用数组模拟hash表
题目其实有提到 fruits[i] 的范围,所以我们不必真的使用unordered_map作为hash表,使用数组模拟即可,这样虽然会浪费空间,但是提高了效率。
class Solution {
public:int totalFruit(vector<int>& fruits) {int hash[100000] = { 0 };//cnt用于统计hash表的水果的种类个数int n = fruits.size(), ret = 0, cnt = 0;for(int left = 0, right = 0; right < n; right++){hash[fruits[right]]++;if(hash[fruits[right]] == 1) cnt++;while(cnt > 2){hash[fruits[left]]--;if(hash[fruits[left++]] == 0) cnt--;}ret = max(ret, right - left + 1);}return ret;}
};
时间复杂度:O(n)
空间复杂度:O(n)
找到字符串中所有字母异位词
题目链接:438. 找到字符串中所有字母异位词
题目描述:
给定两个字符串 s 和 p,找到 s 中所有 p 的 异位词 的子串,返回这些子串的起始索引。顺序可以不考虑。
异位词是指由相同字母重排列形成的字符串(包括相同的字符串)。
解题思路
解法:滑动窗口 + 哈希
因为字符串 p 的异位词的长度一定于字符串 p 的长度相等,所以我们可以在字符串 s 中使用与字符串 p 等长度的滑动窗口来求解。
我们可以使用两个大小为26的数组来模拟哈希表,用于统计窗口内的字母频次和字符串s的字母频次,当比较得到两个哈希表相等时,说明滑动窗口中每种字母的数量与字符 p 每种字母的数量相同,窗口内的字符是字符 p 的一个异位词,此时记录窗口起始索引。
具体过程如下:
- 1.初始化 left 和 right 指针来维护滑动窗口,两个大小为26的数组 hash1 和 hash2 来模拟哈希表,记录字符串 p 的字母频次和窗口字母频次。
- 2.right 向右遍历数组
- right 位置的字母入窗口,将其加入哈希表。
- 当滑动窗口长度大于字符串 p 的长度时,left++,将窗口左侧字母移除同时更新其在哈希表的频次。
- 3.更新结果,当 hash1 与 hash2 相等时,记录窗口起始索引。
注意:判断两个 hash 表是否相等的时间复杂度较高,效率较低。故我们要优化更新结果的判断条件(两个哈希表相等),我们可以来使用一个变量 cnt 记录窗口内的字母相较于字符串 p 的有效字符的数量,并在入窗口和窗口时维护 cnt,这样更新结果时,只需判断 cnt 是否等于字符串 p 的长度就可以知道窗口字符是否是字符串 p 的异位词。
解释下有效字符的数量,其实就是让窗口的组成字母尽可能接近字符 p ,当有效字符的数量等于字符 p 的长度,就说明了窗口的字母频次与字符 p 的字母频次相等,这也是比较两个统计字母频次的哈希表相等的本质,cnt 间接完成了这个任务。
代码实现
class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ret;int n = s.size(), m = p.size();//统计p字符串中每个字母出现的个数int hash1[26] = { 0 };for(auto ch : p) hash1[ch - 'a']++;//统计窗口中每个字母出现的个数int hash2[26] = { 0 };//统计窗口中有效字符的数量int cnt = 0;for(int left = 0, right = 0; right < n; right++){//进窗口 + 维护cntchar in = s[right];hash2[in - 'a']++;if(hash2[in - 'a'] <= hash1[in - 'a']) cnt++;//窗口长度大于字符串p的长度,窗口左端字母出窗口,//并更新cnt和哈希表if(right - left + 1 > m){char out = s[left++];//出窗口 + 维护cntif(hash2[out - 'a'] <= hash1[out - 'a']) cnt--;hash2[out - 'a']--;}//更新结果if(cnt == m) ret.push_back(left);}return ret;}
};
时间复杂度:O(n)
空间复杂度:O(1)
串联所有单词的子串
题目链接:30. 串联所有单词的子串
题目描述:
给定一个字符串 s 和一个字符串数组 words,words 中所有字符串的长度相同。s 中的 串联子串 是指包含 words 中所有字符串以任意顺序排列连接起来的子串。
例如,如果 words = ["ab","cd","ef"],那么 "abcdef", "abefcd", "cdabef", "cdefab", "efabcd" 和 "efcdab" 都是串联子串,而 "acdbef" 不是串联子串,因为它不是 words 排列的连接。
返回所有串联子串在 s 中的开始索引,顺序可以不考虑。
解题思路
解法:滑动窗口 + 哈希表
这道题就是找到字符串中所有字母异位词的升级版,从原来处理单个字符变成了处理单个单词,我们只需要将 words 的单词看成单个字母就行了,然后用滑动窗口 + 哈希表解决。
具体过程:
1.用哈希表 hash1 记录 words 中每个单词的频次。
2.遍历字符串 s ,并用哈希表 hash2 来维护滑动窗口内的单词频次,注意每次增加窗口的大小为单词的长度。
3.当窗口大小大于所有单词的总长度时,出窗口和更新 hash2 。
4.当 hash1 和 hash2 两个哈希表相等时,更新结果。
判断两个哈希表是否相等消耗较大,用 count 来优化,count 统计滑动窗口内有效单词的个数。当 count 与 words 的单词个数相等时,说明找到了符合条件的一个窗口。
代码实现
class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {vector<int> ret;unordered_map<string, int> hash1;for(auto& e : words) hash1[e]++;int len = words[0].size(), m = words.size(), n = s.size();//执行len次滑动窗口for(int i = 0; i < len; ++i){unordered_map<string, int> hash2;for(int left = i, right = i, count = 0; right <= n - len; right += len){//进窗口+维护countstring in(s.begin() + right, s.begin() + right + len);hash2[in]++;if(hash1.count(in) && hash2[in] <= hash1[in]) count++;//判断+出窗口+维护countif(right - left + 1 > m * len){string out(s.begin() + left, s.begin() + left + len);if(hash1.count(out) && hash2[out] <= hash1[out]) count--;hash2[out]--;left += len;}//更新结果if(count == m)ret.push_back(left);}}return ret;}
};
1.执行 len 次滑动窗口(len 是单词长度):由 s 字符串的长度不一定是单词长度的整数倍,需要执行 len 滑动窗口来保证答案的完整性。
2.注意 right 的范围,right 最后一次执行循环的位置应该是在 n - len 处。
时间复杂度:O( n * len),其中 n 是字符串 s 的长度,需要 len 次滑动窗口,每次遍历一次 s。
空间复杂度:O(m * len),m 是单词个数,每次滑动窗口都需要用一个哈希表来存储单词频次。
最小覆盖子串
题目链接:76. 最小覆盖子串
题目描述:
给你一个字符串 s 和一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s
中不存在这样的子串,则返回空字符串 ""
。
注意:
- 对于
t
中重复的字符,最小子串中该字符数量必须不少于t
中的字符数量。 - 如果存在这样的子串,答案是唯一的。
解题思路
解法:滑动窗口+哈希
根据题目,我们直接根据暴力解法来优化,就得到滑动窗口+哈希的解题方法。
具体过程如下:
1.利哈希表 hash1 来统计字符串 t 中每个字符出现的频次。
2.使用滑动窗口遍历字符串 s ,并用哈希表 hash2 来统计窗口中字符频次。
3.当窗口的字符频次满足要求时,更新结果,然后收缩窗口,直到窗口字符频次不满足要求。
注意:这里判断窗口的字符频次满足要求不是判断两个哈希表是否相等,而是 hash1 的字符频次要完整的出现在 hash2 中,hash1 中可以出现除字符串 t 中的字符以外的字符频次。也就是说,窗口内只要完整出现字符串 t 的所有字符即可(字符种类及其对应的频次)。
我们这里还是利用 count 来完成判断,这里的 count 统计的时有效字符的种类,只有 t 中的单个字符在窗口内出现的频次与在 t 中完全一样,count 才自增1,同理,频次不相等时就自减 1,当 count 与 t 中字符种类数相同时,说明找到一个符合条件的覆盖字串,更新结果。
代码实现
class Solution {
public:string minWindow(string s, string t) {string ret;//hash1统计t字符频次和计算hash1的大小,hash1size统计t的字符种类int hash1[128] = { 0 }, hash1size = 0;for(auto e : t) if(hash1[e]++ == 0) hash1size++;//hash2统计窗口字符频次int hash2[128] = { 0 };int len = INT_MAX, start = 0;//count统计有效字符的种类for(int left = 0, right = 0, count = 0; right < s.size(); right++){//进窗口 + 维护countchar in = s[right];if(++hash2[in] == hash1[in]) count++;//判断while(count == hash1size){//更新结果if(right - left + 1 < len){len = right - left + 1;start = left;}//出窗口+维护countchar out = s[left++];if(hash2[out]-- == hash1[out]) count--;}}ret = len == INT_MAX ? "" : s.substr(start, len);return ret;}
};
时间复杂度:O(n)
空间复杂度:O(1)
拜拜,下期再见😏
摸鱼ing😴✨🎞
相关文章:

【算法一周目】滑动窗口(2)
目录 水果成篮 解题思路 代码实现 找到字符串中所有字母异位词 解题思路 代码实现 串联所有单词的子串 解题思路 代码实现 最小覆盖子串 解题思路 代码实现 水果成篮 题目链接:904. 水果成篮 题目描述: 你正在探访一家农场,农场…...
Zustand:一个轻量级的React状态管理库
文章目录 前言一、安装Zustand二、使用Zustand三、实际案例结语 前言 在现代Web开发中,状态管理是一个常见的需求,特别是在构建大型或复杂的单页面应用程序(SPA)时。React等框架虽然提供了基本的状态管理功能,但对于复…...
C++练级计划->《单例模式》懒汉和饿汉
目录 单例模式是什么? 单例模式的应用: 饿汉单例模式: 1.实现: 2.理解: 懒汉单例模式: 1.实现: 2.理解: 懒汉和饿汉的优缺点 饿汉模式的优点: 饿汉模式的缺点&a…...
SQL for XML
关系数据模型与SQL SQL for XML 模式名功能RAW返回的行作为元素,列值作为元素的属性AUTO返回表名对应节点名称的元素,每列的属性作为元素的属性输出输出,可形成简单嵌套结构EXPLICIT通过SELECT语法定义输出XML结构PATH列名或列别名作为XPAT…...

如何使用GCC手动编译stm32程序
如何不使用任何IDE(集成开发环境)编译stm32程序? 集成开发环境将编辑器、编译器、链接器、调试器等开发工具集成在一个统一的软件中,使得开发人员可以更加简单、高效地完成软件开发过程。如果我们不使用KEIL,IAR等集成开发环境,…...

在线绘制Nature Communication同款双色、四色火山图,突出感兴趣的基因
导读:火山图通常使用三种颜色分别表示显著上调,显著下调和不显著。通过为特定的数据点添加另一种颜色,可以创建双色或四色火山图,从而更直观地突出感兴趣的数据点。 《Nature Communication》文章“Molecular and functional land…...

C语言:C语言实现对MySQL数据库表增删改查功能
基础DOME可以用于学习借鉴; 具体代码 #include <stdio.h> #include <mysql.h> // mysql 文件,如果配置ok就可以直接包含这个文件//宏定义 连接MySQL必要参数 #define SERVER "localhost" //或 127.0.0.1 #define USER "roo…...

C++ 二叉搜索树(Binary Search Tree, BST)深度解析与全面指南:从基础概念到高级应用、算法优化及实战案例
🌟个人主页:落叶 🌟当前专栏: C专栏 目录 ⼆叉搜索树的概念 ⼆叉搜索树的性能分析 ⼆叉搜索树的插⼊ ⼆叉搜索树的查找 二叉搜索树中序遍历 ⼆叉搜索树的删除 cur的左节点为空的情况 cur的右节点为空的情况 左,右节点都不为…...

刷题日常(移动零,盛最多水的容器,三数之和,无重复字符的最长子串)
移动零 给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。 请注意 ,必须在不复制数组的情况下原地对数组进行操作。 俩种情况: 1.当nums[i]为0的时候 直接i 2.当nums[i]不为0的时候 此时 …...
深入了解决策树---机器学习中的经典算法
引言 决策树(Decision Tree)是一种重要的机器学习模型,以直观的分层决策方式和简单高效的特点成为分类和回归任务中广泛应用的工具。作为解释性和透明性强的算法,决策树不仅适用于小规模数据,也可作为复杂模型的基石&…...

Elasticsearch对于大数据量(上亿量级)的聚合如何实现?
大家好,我是锋哥。今天分享关于【Elasticsearch对于大数据量(上亿量级)的聚合如何实现?】面试题。希望对大家有帮助; Elasticsearch对于大数据量(上亿量级)的聚合如何实现? 1000道 …...

深度学习模型:循环神经网络(RNN)
一、引言 在深度学习的浩瀚海洋里,循环神经网络(RNN)宛如一颗独特的明珠,专门用于剖析序列数据,如文本、语音、时间序列等。无论是预测股票走势,还是理解自然语言,RNN 都发挥着举足轻重的作用。…...

前端---HTML(一)
HTML_网络的三大基石和html普通文本标签 1.我们要访问网络,需不需要知道,网络上的东西在哪? 为什么我们写,www.baidu.com就能找到百度了呢? 我一拼ping www.baidu.com 就拼到了ip地址: [119.75.218.70]…...

SQL 复杂查询
目录 复杂查询 一、目的和要求 二、实验内容 (1)查询出所有水果产品的类别及详情。 查询出编号为“00000001”的消费者用户的姓名及其所下订单。(分别采用子查询和连接方式实现) 查询出每个订单的消费者姓名及联系方式。 在…...

银河麒麟桌面系统——桌面鼠标变成x,窗口无关闭按钮的解决办法
银河麒麟桌面系统——桌面鼠标变成x,窗口无关闭按钮的解决办法 1、支持环境2、详细操作说明步骤1:用root账户登录电脑步骤2:导航到kylin-wm-chooser目录步骤3:编辑default.conf文件步骤4:重启电脑 3、结语 Ὁ…...

抓包之使用chrome的network面板
写在前面 本文看下工作中非常非常常用的chrome的network面板功能。 官方介绍:地址。 1:前置 1.1:打开 右键-》检查,或者F12。 1.2:组成部分 2:控制器常用功能 详细如下图: 接着我们挑选其…...
避坑ffmpeg直接获取视频fps不准确
最近在做视频相关的任务,调试代码发现一个非常坑的点,就是直接用ffmpeg获取fps是有很大误差的,如下: # GPT4o generated import ffmpegprobe ffmpeg.probe(video_path, v"error", select_streams"v:0", sho…...

大数据新视界 -- 大数据大厂之 Hive 函数库:丰富函数助力数据处理(上)(11/ 30)
💖💖💖亲爱的朋友们,热烈欢迎你们来到 青云交的博客!能与你们在此邂逅,我满心欢喜,深感无比荣幸。在这个瞬息万变的时代,我们每个人都在苦苦追寻一处能让心灵安然栖息的港湾。而 我的…...
深入解析 Django 中数据删除的最佳实践:以动态管理镜像版本为例
文章目录 引言场景与模型设计场景描述 删除操作详解1. 删除单个 Tag2. 批量删除 Tags3. 删除前确认4. 日志记录 高阶优化与问题分析1. 外键约束与误删保护2. 并发删除的冲突处理3. 使用软删除 结合 Django Admin 的实现总结与实践思考 引言 在现代应用开发中,服务和…...
【java】sdkman-java多环境切换工具
#java #env #sdk #lcshand 首先我们来复习一下,可参考我原来的文章: python多个版本的切换可用pyenv nodejs多个版本的切换可用nvm 同样,java多个版本的切换可用sdkman和jenv,我偏重于使用sdkman,因为有时候我也需要…...

【入坑系列】TiDB 强制索引在不同库下不生效问题
文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案
问题描述:iview使用table 中type: "index",分页之后 ,索引还是从1开始,试过绑定后台返回数据的id, 这种方法可行,就是后台返回数据的每个页面id都不完全是按照从1开始的升序,因此百度了下,找到了…...
服务器硬防的应用场景都有哪些?
服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式,避免服务器受到各种恶意攻击和网络威胁,那么,服务器硬防通常都会应用在哪些场景当中呢? 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

CMake 从 GitHub 下载第三方库并使用
有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...
《C++ 模板》
目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板,就像一个模具,里面可以将不同类型的材料做成一个形状,其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式:templa…...
【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制
使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下,限制某个 IP 的访问频率是非常重要的,可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案,使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...

淘宝扭蛋机小程序系统开发:打造互动性强的购物平台
淘宝扭蛋机小程序系统的开发,旨在打造一个互动性强的购物平台,让用户在购物的同时,能够享受到更多的乐趣和惊喜。 淘宝扭蛋机小程序系统拥有丰富的互动功能。用户可以通过虚拟摇杆操作扭蛋机,实现旋转、抽拉等动作,增…...

实战三:开发网页端界面完成黑白视频转为彩色视频
一、需求描述 设计一个简单的视频上色应用,用户可以通过网页界面上传黑白视频,系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观,不需要了解技术细节。 效果图 二、实现思路 总体思路: 用户通过Gradio界面上…...

【堆垛策略】设计方法
堆垛策略的设计是积木堆叠系统的核心,直接影响堆叠的稳定性、效率和容错能力。以下是分层次的堆垛策略设计方法,涵盖基础规则、优化算法和容错机制: 1. 基础堆垛规则 (1) 物理稳定性优先 重心原则: 大尺寸/重量积木在下…...

ubuntu系统文件误删(/lib/x86_64-linux-gnu/libc.so.6)修复方案 [成功解决]
报错信息:libc.so.6: cannot open shared object file: No such file or directory: #ls, ln, sudo...命令都不能用 error while loading shared libraries: libc.so.6: cannot open shared object file: No such file or directory重启后报错信息&…...