汉中微信网站建设推广,中型网站流量,无锡建设管理服务中心,it运维发展方向#x1f31f;快来参与讨论#x1f4ac;#xff0c;点赞#x1f44d;、收藏⭐、分享#x1f4e4;#xff0c;共创活力社区。 #x1f31f; 别再犹豫了#xff01;快来订阅我们的算法每日双题精讲专栏#xff0c;一起踏上算法学习的精彩之旅吧#xff01;#x1f4aa;… 快来参与讨论点赞、收藏⭐、分享共创活力社区。 别再犹豫了快来订阅我们的算法每日双题精讲专栏一起踏上算法学习的精彩之旅吧 今天咱们就一同来探究 “水果成篮” 和 “找到字符串中所有字母异位词” 这两道经典题目看看滑动窗口算法是如何在其中施展魔法的♂️。 目录
水果成篮
题目描述
讲解算法原理
代码实现以 C 为例
找到字符串中所有字母异位词
题目描述 讲解算法原理 代码实现以 C 为例 水果成篮 题目链接【力扣】
题目描述 根据示例分析该题的本质就是找出最长子数组的长度子数组不超过俩种水果类型 讲解算法原理
解法一 我们用暴力解法写一下例如f[1,2,3,2,2]
依次找出所以的情况 代码中我们利用哈希表列举情况用哈希表统计水果出现的类型数
解法二
先分析 当我们用暴力解法时遇到如下情况我们让 left right 回到 left的位置继续列举情况
当left时区间的 kinds 要么不变要么减少一个 当kinds不变时right没有必要改变当kinds减少时right可以继续向后移动 因此我们可以用滑动窗口的解法right不回退嘛
滑动窗口四大步 left0,right0进窗口——right右移动的时候判断 出窗口——就是left右移动的时候更新结果 举例 f[12123233] 每次遍历right,让其放入hash表里面判断有没有超出类型个数
当hash.length2时出窗口 left右移动的时候要根据某个水果种类的数量来进行移动因此我们创建的hash表要有俩个参数一个记录种类一个记录个数
例如下面我们要将left移动到3的前面
代码实现以 C 为例
class Solution {
public:int totalFruit(vectorint fruits) {int hash[100001]{0};//统计窗口内出现了多少种结果int ret0;for(int left0,right0,kinds0;rightfruits.size();right){if(hash[fruits[right]]0) kinds;hash[fruits[right]];//进窗口while(kinds2)//判断{//出窗口hash[fruits[left]]--;if(hash[fruits[left]]0) kinds--;left;}retmax(ret,right-left1);}return ret;}
}; 找到字符串中所有字母异位词 题目链接【力扣】
题目描述 讲解算法原理
1.如何判断俩个字符串是否是异位词 可以先排序再比较但是时间复杂度为nlogn 比较大通过统计字符串中字符出现的个数也可以判断借助hash表即可 2.解决问题
例如
暴力解法
计入p的长度m 在S里依次比较 优化解法
当字符串依次遍历时 我们发现ba重复出现所以我们只要将c从hash表移除让e加入hash表即可滑动窗口 滑动窗口四大步 left0,right0进窗口——right右移动的时候判断 出窗口——就是left右移动的时候更新结果 3.优化更新结果的判断条件
利用变量count来统计窗口中“有效字符”的个数 使用一个数组targetCount来记录字符串p中每个字母的出现次数再使用一个数组windowCount来记录当前窗口内每个字母的出现次数。设一个变量valid来表示窗口内有效字母的数量初始值为0。 然后将right指针向右移动每移动一次就将新字母在windowCount中的计数加1并检查该字母的计数是否等于在targetCount中的计数如果相等则valid加1。当valid等于p中不同字母的数量时说明当前窗口是一个字母异位词。 此时将left指针向右移动同时更新windowCount和valid直到valid小于p中不同字母的数量。在移动left指针的过程中如果窗口内的子串长度等于p的长度就将left指针的索引加入到结果数组中。 重复上述步骤直到right指针走到字符串s的末尾。最后返回结果数组。 代码实现以 C 为例
class Solution {
public:vectorint findAnagrams(string s, string p) {vectorint result;// 如果s的长度小于p的长度直接返回空结果if (s.length() p.length()) return result;// 用于记录字符串p中每个字母的出现次数vectorint targetCount(26, 0);// 用于记录当前窗口内每个字母的出现次数vectorint windowCount(26, 0);int valid 0;// 初始化targetCount数组for (char c : p) {targetCount[c - a];}int left 0, right 0;while (right s.length()) {int rightIndex s[right] - a;// 将新字母在windowCount中的计数加1windowCount[rightIndex];// 如果该字母的计数小于等于在targetCount中的计数说明该字母在窗口内的数量还未超过p中该字母的数量有效字母数量加1if (windowCount[rightIndex] targetCount[rightIndex]) {valid;}// 当窗口大小大于p的长度时移动left指针缩小窗口while (right - left 1 p.length()) {int leftIndex s[left] - a;// 将left指针指向的字母在windowCount中的计数减1windowCount[leftIndex]--;// 如果该字母的计数小于在targetCount中的计数说明该字母在窗口内的数量已经小于p中该字母的数量有效字母数量减1if (windowCount[leftIndex] targetCount[leftIndex]) {valid--;}left;}// 如果有效字母数量等于p中不同字母的数量说明当前窗口是一个字母异位词将left指针的索引加入结果数组if (valid p.length()) {result.push_back(left);}right;}return result;}
}; 我以后还会对 算法 相关知识进行更多的创作欢迎大家关注我一起探索 算法 的奇妙世界
【A Charmer】
