网站搭建项目描述,如何刷关键词指数,wordpress上传mp4,房地产设计图与规划图之前的blog链接#xff1a;https://blog.csdn.net/weixin_43303286/article/details/131700482?spm1001.2014.3001.5501
我用的方法是在leetcode再过一遍例题#xff0c;明显会的就复制粘贴#xff0c;之前没写出来就重写#xff0c;然后从拓展题目中找题目来写。辅以Lab…之前的blog链接https://blog.csdn.net/weixin_43303286/article/details/131700482?spm1001.2014.3001.5501
我用的方法是在leetcode再过一遍例题明显会的就复制粘贴之前没写出来就重写然后从拓展题目中找题目来写。辅以Labuladong的文章看。然后刷题不用CLion了使用leetcode自带模拟面试环境。
76 . 最小覆盖子串
leetcode链接https://leetcode.cn/problems/minimum-window-substring/?envTypestudy-plan-v2envIdtop-100-liked
给你一个字符串 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 的子串中
因此没有符合条件的子字符串返回空字符串。这题的意思就是在s中找到含有t所有字母的最小长度的子串。滑动窗口的思路是这样
1、我们在字符串 S 中使用双指针中的左右指针技巧初始化 left right 0把索引左闭右开区间 [left, right) 称为一个「窗口」。
2、我们先不断地增加 right 指针扩大窗口 [left, right)直到窗口中的字符串符合要求包含了 T 中的所有字符。
3、此时我们停止增加 right转而不断增加 left 指针缩小窗口 [left, right)直到窗口中的字符串不再符合要求不包含 T 中的所有字符了。同时每次增加 left我们都要更新一轮结果。
4、重复第 2 和第 3 步直到 right 到达字符串 S 的尽头。
第 2 步相当于在寻找一个「可行解」然后第 3 步在优化这个「可行解」最终找到最优解。
最终代码
class Solution {
public:string minWindow(string s, string t) {unordered_mapchar, int need, window;for (char c : t) need[c];int left 0, right 0;int valid 0;// 记录最小覆盖子串的起始索引及长度int start 0, len INT_MAX;while (right s.size()) {// c 是将移入窗口的字符char c s[right];// 扩大窗口right;// 进行窗口内数据的一系列更新if (need.count(c)) {window[c];if (window[c] need[c])valid;}// 判断左侧窗口是否要收缩while (valid need.size()) {// 在这里更新最小覆盖子串if (right - left len) {start left;len right - left;}// d 是将移出窗口的字符char d s[left];// 缩小窗口left;// 进行窗口内数据的一系列更新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 的 异位词 的子串返回这些子串的起始索引。
不考虑答案输出的顺序。异位词 指由相同字母重排列形成的字符串包括相同的字符串。示例 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 的异位词。这里差一个unordered_map查找键值对时find和count的区别find一般需要获取具体指count则着重于判断在不在。 最终代码
class Solution {
public:vectorint findAnagrams(string s, string t) {unordered_mapchar, int need, window;for (char c : t) need[c];int left 0, right 0;int valid 0;vectorint res; // 记录结果while (right s.size()) {char c s[right];right;// 进行窗口内数据的一系列更新if (need.count(c)) {window[c];if (window[c] need[c]) valid;}// 判断左侧窗口是否要收缩while (right - left t.size()) {// 当窗口符合条件时把起始索引加入 resif (valid need.size())res.push_back(left);char d s[left];left;// 进行窗口内数据的一系列更新if (need.count(d)) {if (window[d] need[d])valid--;window[d]--;}}}return res;
}};
