芜湖高端网站建设,阿里巴巴网站建设论文,wordpress无法安装这个包,朝阳网站建设 高碑店系列综述#xff1a; #x1f49e;目的#xff1a;本系列是个人整理为了秋招面试的#xff0c;整理期间苛求每个知识点#xff0c;平衡理解简易度与深入程度。 #x1f970;来源#xff1a;材料主要源于【CodeTopHot200】进行的#xff0c;每个知识点的修正和深入主要参… 系列综述 目的本系列是个人整理为了秋招面试的整理期间苛求每个知识点平衡理解简易度与深入程度。 来源材料主要源于【CodeTopHot200】进行的每个知识点的修正和深入主要参考各平台大佬的文章其中也可能含有少量的个人实验自证。 结语如果有帮到你的地方就点个赞和关注一下呗谢谢 【C】秋招实习面经汇总篇 文章目录 基础知识概述 算法例题3. 无重复字符的最长子串239. 滑动窗口最大值76. 最小覆盖子串438. 找到字符串中所有字母异位词 参考博客 点此到文末惊喜↩︎
基础知识
概述
作用 求解线性表数组/字符串中满足条件的连续子区间性质最长/最短等的相关问题通过复用子区间性质的计算结果从而减少循环层数降低时间复杂度 原理 当不满足条件的时候扩大窗口当满足条件之后减小窗口将条件进行使用bool函数封装构建基本算法框架 核心按照条件进行滑动和计算符合条件的窗口性质基本框架 解决的问题 给定一个线性表字符串、数组等一次遍历求满足指定条件的连续子部分 /* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {// 参数的健壮性检查if (s.size() t.size()) return ;// 子区间性质的信息缓存unordered_mapchar, int need, window;for (char c : t) need[c];int valid 0; // 算法int left 0, right 0;while (right s.size()) {// c 是将移入窗口的字符char c s[right];// 右移窗口right;// 进行窗口内数据的一系列更新.../*** debug 输出的位置 ***/printf(window: [%d, %d)\n, left, right);/********************/// 判断左侧窗口是否要收缩while (window needs shrink) {// d 是将移出窗口的字符char d s[left];// 左移窗口left;// 进行窗口内数据的一系列更新...}}
}算法例题
3. 无重复字符的最长子串
问题 给定一个字符串 s 请你找出其中不含有重复字符的 最长子串 的长度。 思路 滑动窗口
int Template(string s) {// 健壮性检查if(s.size() 0) return 0;// TODO记录窗口子区间性质int max_len 0;unordered_setchar windows;// 初始化int left 0, right 0;while (right s.size()) {// 缩小窗口while (windows.count(s[right]) ! 0){windows.erase(s[left]);left;} // 增大窗口windows.insert(s[right]);right;max_len max(max_len, right-left); // TODO更新子区间性质}return max_len;
}239. 滑动窗口最大值
题目
class Solution {
private:class MyQueue { //单调队列从大到小public:dequeint que; // 使用deque来实现单调队列// 每次弹出的时候比较当前要弹出的数值是否等于队列出口元素的数值如果相等则弹出。// 同时pop之前判断队列当前是否为空。void pop (int value) {if (!que.empty() value que.front()) {que.pop_front();}}// 如果push的数值大于入口元素的数值那么就将队列后端的数值弹出直到push的数值小于等于队列入口元素的数值为止。 // 这样就保持了队列里的数值是单调从大到小的了。void push (int value) {while (!que.empty() value que.back()) {que.pop_back();}que.push_back(value);}// 查询当前队列里的最大值 直接返回队列前端也就是front就可以了。int front() {return que.front();}};
public:vectorint maxSlidingWindow(vectorint nums, int k) {MyQueue que;vectorint result;for (int i 0; i k; i) { // 先将前k的元素放进队列que.push(nums[i]);}result.push_back(que.front()); // result 记录前k的元素的最大值for (int i k; i nums.size(); i) {que.pop(nums[i - k]); // 滑动窗口移除最前面元素que.push(nums[i]); // 滑动窗口前加入最后面的元素result.push_back(que.front()); // 记录对应的最大值}return result;}
};76. 最小覆盖子串
题目 返回字符串 s 中包含字符串 t 的全部字符的最小窗口 思路 不断滑动增加窗口当窗口满足条件时开始收缩并记录窗口的起始位置和长度
string SlideWindow(string s, string t) {// 窗口性质need记录子串情况window记录合适窗口unordered_mapchar, int need, window; // need记录目标窗口状态window记录当前窗口状态for (char c : t) need[c]; // 子串中可能出现重复字母int valid 0; // 目标窗口和当前窗口符合字符的大小int start 0, len INT_MAX; // 符合条件子串的起始位置和长度// 初始化及滑动窗口算法int left 0, right 0;while (right s.size()) {char c s[right]; // c 是将移入窗口的字符right; // 右移窗口// 进行窗口内数据的一系列更新if (need.count(c)) {window[c];if (window[c] need[c])valid;}while (valid need.size()) { // TODO收缩条件// TODO更新结果记录if (right - left len) { start left;// 更新起始值len right - left;// 最小长度}// 收缩窗口char d s[left];left;// TODO收缩处理if (need.count(d)) {if (window[d] need[d])valid--;window[d]--;} }}// 返回最小覆盖子串return len INT_MAX ? : s.substr(start, len);
}438. 找到字符串中所有字母异位词
问题 给定两个字符串 s 和 p找到 s 中所有 p 的 异位词 的子串返回这些子串的起始索引。异位词 指由相同字母重排列形成的字符串包括相同的字符串。 思路 快慢指针 交换
// 返回字符串 s 中包含字符串 t 的全部字符的最小窗口
string SlideWindow(string s, string t) {// need记录子串情况window记录合适窗口unordered_mapchar, int need, window;for (char c : t) need[c];int left 0, right 0;// 记录最小覆盖子串的起始索引及长度int start 0, len INT_MAX;int valid 0;while (right s.size()) {char c s[right]; // c 是将移入窗口的字符right; // 右移窗口// 进行窗口内数据的一系列更新if (need.count(c)) {window[c];if (window[c] need[c])valid;}while (valid need.size()) { // TODO收缩条件// TODO更新结果记录if (right - left len) { start left;// 更新起始值len right - left;// 最小长度}// 收缩窗口char d s[left];left;// TODO收缩处理if (need.count(d)) {if (window[d] need[d])valid--;window[d]--;} }}// 返回最小覆盖子串return len INT_MAX ? : s.substr(start, len);
}少年我观你骨骼清奇颖悟绝伦必成人中龙凤。 不如点赞·收藏·关注一波 点此跳转到首行↩︎
参考博客 labuladong的leetcode滑动窗口模板 codetop
