潮州住房和城乡建设局网站,八大恶心的网站制作,京东集团官网首页,全国旅游服务平台代码模板#xff1a;
//滑动窗口伪代码
class Solution {
public:int minWindow(string s) {// 同方向移动#xff0c;起始的时候#xff0c;都位于 0#xff0c;表示我们定义搜索区间为 [left, right) #xff0c;此时区间为空区间int left 0;int right 0;while(right…代码模板
//滑动窗口伪代码
class Solution {
public:int minWindow(string s) {// 同方向移动起始的时候都位于 0表示我们定义搜索区间为 [left, right) 此时区间为空区间int left 0;int right 0;while(right Slen){//每一次循环的开始都一定不满足条件//因为上一次循环是从满足条件跳出while的// 这里对状态做修改好让程序在后面检测到满足条件right; //右移right,实际上这一句也可以写在外层while的最后一句while(满足条件){ // 对状态做修改好让程序在后面检测到不满足条件left; //右移left}//记录当前最接近结果的值}return maxlen;}
}; 例题1leecode第3题无重复字符的最长子串
给定一个字符串 s 请你找出其中不含有重复字符的 最长 子串 的长度。
示例 1:
输入: s abcabcbb
输出: 3
解释: 因为无重复字符的最长子串是 abc所以其长度为 3。示例 2:
输入: s bbbbb
输出: 1
解释: 因为无重复字符的最长子串是 b所以其长度为 1。示例 3:
输入: s pwwkew
输出: 3
解释: 因为无重复字符的最长子串是 wke所以其长度为 3。请注意你的答案必须是 子串 的长度pwke 是一个子序列不是子串。提示
0 s.length 5 * 104 s 由英文字母、数字、符号和空格组成
解答
class Solution {
public:int lengthOfLongestSubstring(string s) {int len s.size();if(len 2){return len;}int *freq new int[128];for(int i 0; i 128; i){freq[i] 0;}int maxlen 1;//维护一个变量用于记录最长字符串的长度int left 0, right 0;//循环不变量 [left, right无重复字符串while(right len){freq[s[right]]; // 对状态做修改好让程序在后面检测到满足条件:[left, right出现重复元素right;while(freq[s[right-1]] 2){//满足条件[left, right出现重复元素freq[s[left]]--;left; }maxlen maxlen (right - left) ? (right - left) : maxlen;//记录当前最接近结果的值}return maxlen;}
};例题2lecoode第76题最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串则返回空字符串 “” 。
注意
对于 t 中重复字符我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 如果 s 中存在这样的子串我们保证它是唯一的答案。
示例 1
输入s ADOBECODEBANC, t ABC
输出BANC
解释最小覆盖子串 BANC 包含来自字符串 t 的 A、B 和 C。示例 2
输入s a, t a
输出a
解释整个字符串 s 是最小覆盖子串。示例 3:
输入: s a, t aa
输出:
解释: t 中两个字符 a 均应包含在 s 的子串中
因此没有符合条件的子字符串返回空字符串。提示
m s.length
n t.length
1 m, n 105
s 和 t 由英文字母组成进阶你能设计一个在 o(mn) 时间内解决此问题的算法吗
解答
class Solution {
public:string minWindow(string s, string t) {int s_len s.size();int t_len t.size();int count 0; //记录t包含的字母个数vectorint MinWindow(128, 0); //记录滑动窗口各个字母出现的次数vectorint CharArray(128, 0); //记录t包含各个字母出现的次数//记录t每个字母出现的次数for(int i 0; i t_len; i){CharArray[t[i]];}//记录t有多少个字母for(int i 0; i 128; i){if(CharArray[i] 0){count;}}int left 0; //滑动窗口的左边int right 0; //滑动窗口的右边int m_left 0; //记录最小子串在s的起始位置int minLen s_len 1; //记录最小子串的长度int sameNumber 0; //记录s中与t相同的字母的个数while(right s_len){char rc s[right];//这个字母在t中出现if(CharArray[rc] 0){//将这个字母加入到记录滑动窗口的数组中MinWindow[rc];//此时这个字母在s出现的次数等于在t出现的次数即s中这个字母满足覆盖t子串的要求if(MinWindow[rc] CharArray[rc]){sameNumber;}}right;//当s中满足t中所有出现的字母要求while(sameNumber count){//维护当前最小字符串的起始和偏移if(minLen right - left){minLen right - left;m_left left;}char lc s[left];//对滑动窗口将要做边界右移会造成的状态进行统计if(CharArray[lc] 0){--MinWindow[lc];if(MinWindow[lc] CharArray[lc]){--sameNumber;}}//滑动窗口左边界右移left;}}//如果没进入sameNumber count循环证明s是不满足包含t的条件则返回空字符串return minLen 1 s_len ? : s.substr(m_left, minLen);}
};例题3leecode lcr第8题长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl1, …, numsr-1, numsr] 并返回其长度。如果不存在符合条件的子数组返回 0 。
示例 1
输入target 7, nums [2,3,1,2,4,3]
输出2
解释子数组 [4,3] 是该条件下的长度最小的子数组。示例 2
输入target 4, nums [1,4,4]
输出1示例 3
输入target 11, nums [1,1,1,1,1,1,1,1]
输出0提示
1 target 109
1 nums.length 105
1 nums[i] 105解答
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int len nums.size();//先判断特殊情况如果数组总和都小于targer则返回0(即示例3的情况)int sum 0;for(int i 0; i len; i){sum nums[i];}if(sum target) return 0;int WindowSum 0; //记录当前窗口的元素和int min_len len; //维护一个最小长度int left 0, right 0;while(right len){WindowSum nums[right];right;while(WindowSum target){min_len (min_len right - left) ? min_len : (right - left);WindowSum - nums[left];left;}}return min_len;}
};例题4leecode 438. 找到字符串中所有字母异位词固定窗口大小的滑动窗口问题
给定两个字符串 s 和 p找到 s 中所有 p 的 异位词 的子串返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串包括相同的字符串。
示例 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 的异位词。提示:
1 s.length, p.length 3 * 104
s 和 p 仅包含小写字母解答
class Solution {
public:vectorint findAnagrams(string s, string p) {int s_len s.size();int p_len p.size(); vectorint res;//记录结果使用if(s_len p_len) return res;vectorint freq_p(26, 0);vectorint window_freq(26, 0);//统计p的频数for(int i 0; i p_len; i){freq_p[p[i] - a];}//窗口的长度固定为p的长度并统计窗口在最初始的频数int left 0, right p_len - 1;for(int i 0; i p_len; i){window_freq[s[i] - a];}while(right s_len - 1 ){int isEq IsArrEq(window_freq, freq_p);if(isEq){res.push_back(left);}//移动窗口并统计移动后的频数window_freq[s[left] - a]--;left;window_freq[s[right 1] - a];right;}//跳出循环后还要单独判断一下移动到s最右侧的情况int isEq IsArrEq(window_freq, freq_p);if(isEq){res.push_back(left);}return res;}
//此函数用于判断两个频数数组是否相等int IsArrEq(vectorint arr1, vectorintarr2){for(int i 0; i 26; i){if(arr1[i] ! arr2[i])return 0;}return 1;}
};
