免费的旅游网站模板,沈阳看男科哪里医院男科好,网络工程干什么的,网站开发 python 工具1. 滑动窗口简介
滑动窗口是一种在算法中常用的技巧#xff0c;主要用来处理具有连续性的子数组或子序列问题。通过滑动窗口#xff0c;可以在一维数组或字符串上维护一个固定或可变长度的窗口#xff0c;逐步移动窗口#xff0c;避免重复计算#xff0c;从而提升效率。常…1. 滑动窗口简介
滑动窗口是一种在算法中常用的技巧主要用来处理具有连续性的子数组或子序列问题。通过滑动窗口可以在一维数组或字符串上维护一个固定或可变长度的窗口逐步移动窗口避免重复计算从而提升效率。常用于求解子数组的最大/最小值、满足条件的子数组个数等问题。
滑动窗口的两种类型
1. 固定大小的滑动窗口窗口大小固定不变通常适合于问题中要求找定长子数组的最大值、最小值等情况。 2. 可变大小的滑动窗口窗口大小根据条件动态调整通常适用于子数组和达到一定值或满足特定条件的情况。
滑动窗口的实现步骤
以可变大小的滑动窗口为例一般步骤如下
1. 初始化窗口的左右边界例如 left 和 right 指针并根据问题需求定义窗口内需要维护的变量如窗口内的和、计数等。 2. 移动右边界 right将新元素加入窗口并更新窗口内的变量。 3. 检查当前窗口是否满足条件。如果满足记录答案如更新最大/最小值然后移动左边界 left 以缩小窗口继续寻找其他符合条件的窗口。 4. 重复步骤 2 和 3直到右边界遍历完数组。
应用场景
滑动窗口常用于以下几类问题 - 子数组和问题如最大、最小和 - 子字符串问题如最长无重复子串 - 符合条件的区间统计
这种方法在处理需要频繁访问连续子序列的问题时具有高效性。
2. 长度最小的子数组
一、题目介绍 二、思路解析
方法一暴力枚举 枚举 将数组中的每个元素 都当做起点向后遍历数组寻找最短区间最后找到将所有元素当做期待所得结果的最小值。
优化方法滑动窗口
由于此问题分析的对象是「⼀段连续的区间」因此可以考虑「滑动窗口」的思想来解决这道题。
1left 0, right 0
2进窗口
- 当窗口中的值小于target是进窗口
3判断什么时候出窗口并更新结果
- 当窗口中的值大于等于target时窗口中的值减去left位置的值更新结果出窗口left
三、代码实现
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int n nums.size(), sum 0, len INT_MAX;for (int left 0, right 0; right n; right){sum nums[right];//进窗口while (sum target) // 判断{len min(len, right - left 1); // 更新结果sum - nums[left]; // 出窗口}}return len INT_MAX ? 0 : len;}
};
. - 力扣LeetCode 为何滑动窗口可以解决问题并且时间复杂度更低 - 这个窗口寻找的是以当前窗口最左侧元素记为 left1 为基准符合条件的情况。也就是在这道题中从 left1 开始满足区间和 sum target 时的最右侧记为right1 能到哪里。 - 我们既然已经找到从 left1 开始的最优的区间那么就可以大胆舍去 left1 。但是如 果继续像方法一⼀样重新开始统计第二个元素 left2 往后的和势必会有大量重复 的计算。 - 此时 rigth1 的作用就体现出来了我们只需将 left1 这个值从 sum 中剔除。从right1 这个元素开始往后找满足 left2 元素的区间此时 right1 也有可能是满足的因为 left1 可能很小。 sum 剔除掉 left1 之后依旧满足大于等于target 。这样我们就能省掉大量重复的计算。 这样我们不仅能解决问题而且效率也会大大提升。 时间复杂度虽然代码是两层循环但是我们的 left 指针和 right 指针都是不回退的两者 最多都往后移动 n 次。因此时间复杂度是 O(N) 总结一下优化算法将每次找到符合条件的区间right都需要重新从新left位置开始遍历数组这一过程省去了。 3. 无重复字符的最长子串
一、题目介绍 二、思路解析
方法一暴力枚举 哈希表 枚举 从每⼀个位置 开始往后无重复字符的子串可以到达什么位置。找出其中长度最大的即 可。在往后寻找无重复子串能到达的位置时可以利用「哈希表」统计出字符出现的频次来判断什么时候子串出现了重复元素 方法二滑动窗口 哈希表
1left 0, right 0
- 定义一个数组模拟哈希表来记录每个字符出现的次数。
2进窗口
- 每当字符串出现一次时数组中对应位置大小1来记录字符出现的次数
3判断什么时候出窗口并更新结果
- hash[s[right]]大于1那就说明此时字符s[right]与 [left到right) 之间的字符有重复。这时开始移动left出窗口并且hash[s[left]]-1这样当left移动到有重复的字符并-1时循环结束。开始更新结果。
- hash[s[right]]没有超过1则说明没有窗口间重符字符更新结果继续移动窗口right
三、代码实现
class Solution {
public:int lengthOfLongestSubstring(string s) {int hash[128] { 0 };int left 0, right 0, n s.size();int ret 0;while (right n){hash[s[right]];while (hash[s[right]] 1)hash[s[left]]--;ret max(ret, right - left 1);right;}return ret;}
};
. - 力扣LeetCode
4. 最大连续1的个数|||
一、题目介绍 二、思路解析 这道题可以转换为 找到数组中不超过包含k个0的的最长连续区间。既然是连续区间可以考虑使用「滑动窗口」来解决问题。 滑动窗口
1left 0, right 0
- 初始化leftrightzero。
2进窗口
- 遍历数组当该元素是0时zero进窗口。
3判断什么时候出窗口并更新结果
- 如果此时zero大于kleft开始移动出窗口直到窗口中的0小于k循环结束后更新结果。
- zero不大于k则继续进窗口不断更新最长连续空间的最大值。
三、代码实现
class Solution {
public:int longestOnes(vectorint nums, int k) {int left 0, right 0, zero 0;int ret 0, n nums.size();while (right n){if (nums[right] 0) zero; //进窗口while (zero k)if(nums[left] 0) zero--;//出窗口ret max(ret, right - left 1); //更新结果right;}return ret;}
};
. - 力扣LeetCode
5. 将x减小到零的最小操作
一、题目介绍 二、思路解析 我们可以转化成求数组内⼀段连续的、和为 sum(nums) - x 的最长数组。此时就是熟悉的「滑动窗口」问题了 滑动窗口 哈希表
1left 0, right 0
- 定义一个tmp用来存储当前窗口中的数之和len来存储最长窗口
2进窗口
- 当right n 时tmp不断的加上当前right位置的值进窗口
3判断什么时候出窗口并更新结果
- 当窗口中的值tmp大于target时tmp减去left位置的值left出窗口。如果窗口重的值等于target则更新结果。
三、代码实现
class Solution {
public:int minOperations(vectorint nums, int x) {int left 0, right 0;int sum 0, n nums.size();for (int e : nums) sum e;int target sum - x;if (target 0) return -1;else if (target 0) return n;int tmp 0, len -1;while (right n){ tmp nums[right];// 入窗口while (tmp target) tmp - nums[left]; //出窗口if (tmp target) len max(len, right - left 1); //更新结果right;}if (len -1) return -1;else return n - len;}
};
. - 力扣LeetCode
6. 水果成篮
一、题目介绍 注意0、1、2、3分别表示是一种水果,而不是拥有水果的类型。例如0表示苹果1表示香蕉2表示西瓜3表示鸭梨
二、思路解析 研究的对象是⼀段连续的区间可以使⽤「滑动窗口」思想来解决问题。 暴力枚举 哈希表 枚举 将数组中的每一个元素都当做起点开始向后遍历直到哈希表中的值大于2比较所有枚举结果中的最大数目
滑动窗口 哈希表
1left 0, right 0
- 定义一个哈希表用来记录窗口中采摘水果的中类
2进窗口
- 每采摘一棵树该树代表的水果对应哈希表中的位置1进窗口。
3判断什么时候出窗口并更新结果
- 当hash的大小大于2时说明此时窗口中的水果的种类超过了两种这时开始移动left出窗口hash[left]--当hash[left] 等于0时说明窗口内没有这种水果了删除hash表中的该种水果更新结果。
- 当hash的大小不大于2说明此时窗口内水果的种类没有超过2则更新结果继续进窗口
三、代码实现
class Solution {
public:int totalFruit(vectorint fruits) {unordered_mapint, int hash; //统计窗口内出现了几种水果int left 0, right 0;int n fruits.size(), ret 0;while (right n){hash[fruits[right]]; // 进窗口while (hash.size() 2) //判断{//出窗口hash[fruits[left]]--;if (hash[fruits[left]] 0)hash.erase(fruits[left]);left;}ret max(ret, right - left 1);//更新结果right;}return ret;}
};
. - 力扣LeetCode
7. 找到字符串中所有字母异位词
一、题目介绍 二、思路解析 - 因为字符串 p 的异位词的长度⼀定与字符串 p 的长度相同所以我们可以在字符串 s 中构 造⼀个长度为与字符串 p 的长度相同的滑动窗口并在滑动中维护窗口中每种字母的数量 - 当窗口中每种字母的数量与字符串 p 中每种字母的数量相同时则说明当前窗口为字符串 p 的异位词 - 因此可以用两个大小为 26 的数组来模拟哈希表⼀个来保存 s 中的子串每个字符出现的个 数另⼀个来保存 p 中每⼀个字符出现的个数。这样就能判断两个串是否是异位词。 暴力枚举 哈希表
枚举 字符串中每三个字符 和p进行比较。用hash表记录每三个字符的种类和数量和p进行比较。
滑动窗口 哈希表
1left 0, right 0
定义两个hash表一个用来保存 s 中的子串每个字符出现的个数另⼀个来保存 p 中每⼀个字符出现的个数。再定义一个count用来表示窗口中符合p的异位词的个数
2进窗口
- for循环每循环一次进一次窗口
3判断什么时候出窗口并更新结果
- 刚进窗口的字符是p中的异位词并且此时窗口中该字符的数量小于p中该字符的数量例如如果刚进窗口中字符是ap中也有一个a并且窗口前两个字符都不是a。符合条件count表示窗口中是p中异位词的数量多了一个。如果此时窗口中该字符的数量大于p中该字符的数量则不符合条件例如窗口中【a, b, a】p中【a, b , c】。
- 刚进窗口中的字符不是p中的异位词hash2[in- a] hash1[in - a]也不成立例如进窗口的字符是d那么hash2【d - a】 1而p中没有d那么hash1【d - ‘a’】 0定义hash表示所有元素初始化为0出现一次1
- 当窗口大小大于p的大小时移动left此时出窗口的字符如果是p的异位词并且窗口中该字符的数量不多于p中该字符的数量例如上面的【a, b, a】当移走第一个a时hash表中字符a所在位置的大小为2就不执行count--count--窗口中是p的异位词的数量-1最后hash表中left移动前所在位置-1出窗口。
- 当count p的大小时说明窗口中都是p的异位词
三、代码实现
class Solution {
public:vectorint findAnagrams(string s, string p) {vectorint ret;//统计字符串p中每个字符的个数int hash1[26] { 0 };for (auto e : p) hash1[e- a];//统计滑动窗口中中每个字符的个数int hash2[26] { 0 };int count 0;for (int left 0, right 0; right s.size(); right){char in s[right];hash2[in - a];//进窗口if (hash2[in- a] hash1[in - a]) count;//维护countif (right - left 1 p.size()){char out s[left];if (hash2[out - a] hash1[out - a]) count--;//维护counthash2[out - a]--;//出窗口}//更新结果if (count p.size()) ret.push_back(left);}return ret;}
};
. - 力扣LeetCode
8. 串联所有单词的子串
一、题目介绍 二、思路解析 如果我们把每⼀个单词看成⼀个⼀个字母问题就变成了找到「字符串中所有的字母异位词」。无 非就是之前处理的对象是⼀个⼀个的字符我们这里处理的对象是⼀个⼀个的单词。小伙伴们可以照着上题的思路自己想一想做一做做题思路这里不再赘述。 . - 力扣LeetCode 三、代码实现
class Solution {
public:vectorint findSubstring(string s, vectorstring words) {vectorint ret;//跑存words中所有字符串的个数unordered_mapstring, int hash1;for (auto st: words) hash1[st];int n words[0].size(), m words.size();for (int i 0; i n; i){unordered_mapstring, int hash2;for(int left i, right i, count 0; right n s.size(); right n){string in s.substr(right, n);hash2[in];// 入窗口if (hash1[in] hash2[in] hash1[in]) count;// 维护count//判断if (right - left 1 n * m) {string out s.substr(left, n);if (hash1[out] hash2[out] hash1[out]) count--;// 维护counthash2[out]--;//出窗口left n;}if (count m) ret.push_back(left);}}return ret;}
};
9. 最小覆盖子串
一、题目介绍 二、思路解析 研究对象是连续的区间因此可以尝试使用滑动窗口的思想来解决。 如何判断当前窗口内的所有字符是符合要求的呢 - 我们可以使用两个哈希表其中⼀个将目标串的信息统计起来另⼀个哈希表动态的维护窗口 内字符串的信息。 - 当动态哈希表中包含目标串中所有的字符并且对应的个数都不小于目标串的哈希表中各个字 符的个数那么当前的窗口就是⼀种可行的方案。 暴力枚举 哈希表
枚举 从中的每个字符开始向后遍历数组直到找到覆盖t的位置比较枚举的所有结果选取最小值。
滑动窗口 哈希表
1left 0, right 0
定义两个hash表⼀个将目标串的信息统计起来另⼀个哈希表动态的维护窗口内字符串的信息。定义一个kind统计目标传中字符的种类。定义count统计窗口中能够覆盖t的字符种类的数量。
2进窗口
for循环进窗口
3判断什么时候出窗口和更新结果
- 只有当窗口中的某一字符数等于t中的该字符的个数时count才会1例如t中有两个A那么只有窗口中出现第二个A时才会执行count第一个A出现时不会执行count。
- 当count kind时说明此时窗口可以覆盖字符串t更新结果记录下此时窗口的起始位置和窗口的长度。然后判断是否count--移动lefthash[left]--出窗口。
三、代码实现
class Solution {
public:string minWindow(string s, string t) {string ret;int hash1[128] { 0 };// 统计t中每个字符出现的次数int kinds 0; // 统计t中字符的种类for (auto e : t) if ( hash1[e] 0 ) kinds;int hash2[128] { 0 }; // 统计s中每个字符出现的次数int n s.size(), m t.size();int minlen INT_MAX, begin -1;for (int left 0, right 0, count 0; right n; right){char in s[right];hash2[in]; // 入窗口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--;//维护counthash2[out]--;//出窗口}}if (begin -1) return ;else return s.substr(begin, minlen);}
};
. - 力扣LeetCode
