西安手机定制网站建设,谷歌搜索引擎入口,自己的网站怎么赚钱,网站运营工资目录小结以及代码框架76. 最小覆盖子串滑动窗口代码以及注释567. 字符串的排列滑动窗口438. 找到字符串中所有字母异位词3. 无重复字符的最长子串化简框架reference小结以及代码框架
滑动窗口技巧属于双指针技巧。 该算法的思路为维护一个窗口#xff0c;不断滑动#xff0c… 目录小结以及代码框架76. 最小覆盖子串滑动窗口代码以及注释567. 字符串的排列滑动窗口438. 找到字符串中所有字母异位词3. 无重复字符的最长子串化简框架reference 小结以及代码框架
滑动窗口技巧属于双指针技巧。 该算法的思路为维护一个窗口不断滑动然后更新答案。 大致框架如下[参考labuladong的算法小抄]
int left 0, right 0;while(right s.size())
{//增大窗口window.add(s[right]);right;while(window needs shrink){//缩小窗口window.remove(s[left]);left;}
}主要的细节问题 1、如何向窗口中添加新元素 2、如何缩小窗口 3、在窗口滑动的哪个阶段更新结果
//滑动窗口算法框架
void slidingWindow(string s, string t)
{unordered_mapchar,int need, window;for(char c : t) need[c];int left 0, right 0;int valid 0;while(right s.size()){//c是将要移入窗口的元素char c s[right];//右移窗口right;//进行窗口内数据更新(右移窗口)/*******************//**debug输出位置***/cout window:[ left , right ]endl;/******************///判断左侧窗口是否需要收缩while(window needs shrink){//d是将移出窗口的字符char d s[left];//左移窗口left;//进行窗口内数据的一系列更新(左移窗口)}}
}76. 最小覆盖子串
https://leetcode-cn.com/problems/minimum-window-substring/ 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串则返回空字符串 “” 。
注意如果 s 中存在这样的子串我们保证它是唯一的答案。 示例 1 输入s “ADOBECODEBANC”, t “ABC” 输出“BANC” 示例 2 输入s “a”, t “a” 输出“a” 提示 1 s.length, t.length 10^5 s 和 t 由英文字母组成
滑动窗口
1、初始化window和need两个哈希表记录下窗口中的字符以及需要凑齐的字符
unordered_mapchar,int need,window;
for(char c : t) need[c];2、使用left和right变量初始化窗口两端区间是左闭右开初始情况下窗口内是没有元素的。
int left 0, right 0;
while(right s.size())
{//开始滑动
}3、定义记录变量 valid_length表示window内满足need条件的字符个数如果valid_length need.size() 说明窗口已经满足了条件已经完全覆盖了串T。
int valid_length;在right向右扩充的时候对新进来的元素进行检查如果它是need中的元素window中对应这个元素就要1然后判断window中这个元素的个数是不是need中这个元素的个数相同如果相同说明这个元素在window中已经找完了这时候就需要将valid_length1了 4、套用模板 确定四个问题的具体细节 1、当right移动扩大window应该更新哪些数据 更新window计数器 2、当left移动缩小window应该更新哪些数据 更新window计数器 3、什么条件下暂停扩大window开始移动left缩小window 当valid长度等于need大小时应该收缩窗口 4、结果应该在扩大窗口时还是缩小窗口时进行 缩小窗口的时候进行更新结果 代码以及注释
class Solution {
public:string minWindow(string s, string t) {unordered_mapchar,int window,need;//记录下t中有哪些元素以及每个元素的个数for(char c : t) need[c];//初始化窗口边界int right 0, left 0;//window满足need条件的元素个数int valid_length 0;//结果字符串在s中的起始地址以及长度这样就不要每次更新整个string了int start 0 , length INT_MAX;while(right s.size()){//******************扩充窗口**************//扩充窗口right;//扩充进来的新元素char c s[right - 1]; //判断该元素是否是need中元素if(need.count(c)){window[c];if(window[c] need[c]) valid_length;}//*******************缩小窗口*************//如果need中所有元素都在window内并且每个元素的频数也与window内元素频数相同那么此时就得到了一个答案记录答案然后缩小窗口以获得更优的答案while(valid_length need.size()){//如果此次答案比上次的答案长度要小我们才更新答案if(right - left length){start left;length right - left;}//左边界向左移动left;//d是刚移出窗口的元素char d s[left - 1];//如果need中出现了dif(need.count(d)){//如果之前d元素在window和need出现的频数相同if(window[d] need[d]){//删除了之后频数不相同了所以这个元素也就不满足了。valid_length--;}window[d]--;}}}//如果length没有更新说明s不存在t中字符或者不满足字符频数返回空字符串否则使用substr将子串返回return length INT_MAX ? : s.substr(start,length);}
};567. 字符串的排列
https://leetcode-cn.com/problems/permutation-in-string/ 给定两个字符串 s1 和 s2写一个函数来判断 s2 是否包含 s1 的排列。
换句话说第一个字符串的排列之一是第二个字符串的子串。
示例1: 输入: s1 “ab” s2 “eidbaooo” 输出: True 解释: s2 包含 s1 的排列之一 (“ba”). 示例2: 输入: s1 “ab” s2 “eidboaoo” 输出: False 注意
输入的字符串只包含小写字母 两个字符串的长度都在 [1, 10,000] 之间
滑动窗口
精确化题目为假设给你一个S和T请问S中是否存在一个子串包含T中所有字符且不包含其他字符 精确化本题细节 1、移动left缩小窗口的时机:窗口大小大于t的大小因为各种排列的长度应该是一样的。 2、当valid_length need.size()时说明窗口中的数据是一个合法的数据应该立即返回true
class Solution {
public:bool checkInclusion(string s1, string s2) {unordered_mapchar,int window,need;for(char c : s1) need[c];int left 0,right 0;int valid_length 0;while(right s2.size()){//扩充windowright;char c s2[right - 1];if(need.count(c)){window[c];if(window[c] need[c]) valid_length;}//缩小windowwhile(right - left s1.size()){if(valid_length need.size()) return true;left;char d s2[left - 1];if(need.count(d)){if(window[d] need[d]) valid_length--;window[d]--;}}}return false;}
};438. 找到字符串中所有字母异位词
https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/ 给定一个字符串 s 和一个非空字符串 p找到 s 中所有是 p 的字母异位词的子串返回这些子串的起始索引。
字符串只包含小写英文字母并且字符串 s 和 p 的长度都不超过 20100。
说明 字母异位词指字母相同但排列不同的字符串。 不考虑答案输出的顺序。 示例 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” 的字母异位词。 直接套模板
class Solution {
public:vectorint findAnagrams(string s, string p) {if(s.empty()) return {};vectorint result;unordered_mapchar,int need,window;for(char c : p) need[c];int left 0,right 0;int valid_length 0;while(right s.size()){//expand windowright;char c s[right - 1];if(need.count(c)){window[c];if(window[c] need[c]){valid_length;}}//shrink windowwhile(right - left p.size()){if(valid_length need.size()){result.emplace_back(left);}left;char d s[left - 1];if(need.count(d)){if(window[d] need[d]){valid_length--;}window[d]--;}}}return result;}
};3. 无重复字符的最长子串
之前做过这次用滑动窗口模板做 https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/ 给定一个字符串请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: s “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”所以其长度为 3。 示例 2: 输入: s “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”所以其长度为 1。 示例 3: 输入: s “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”所以其长度为 3。 请注意你的答案必须是 子串 的长度“pwke” 是一个子序列不是子串。 示例 4: 输入: s “” 输出: 0 提示
0 s.length 5 * 10^4 s 由英文字母、数字、符号和空格组成.
化简框架
将need、valid去除更新窗口数据只需要更新window计数器。 当window[c]大于1说明窗口内存在重复字符不符合条件就应该移动left缩小窗口。 对于更新结果:更新结果的操作放在收缩窗口之后因为收缩之后窗口不存在重复字符。
class Solution {
public:int lengthOfLongestSubstring(string s) {if(s.empty()) return 0;int res 0;unordered_mapchar,int window;int left 0, right 0;while(right s.size()){//expand windowright;char c s[right -1];window[c];//如果进入窗口的新元素在窗口内有重复元素就需要移动left//shrink windowwhile(window[c] 1){left;window[s[left - 1]]--;}res max(res,right - left);}return res;}
};reference 《labuladong的算法小抄》
