HOT100与剑指Offer

---

前言

一个本硕双非的小菜鸡，备战24年秋招，计划刷完hot100和剑指Offer的刷题计划，加油！
根据要求，每一道题都要写出两种以上的解题技巧。

一、239. 滑动窗口最大值（HOT100）

239. 滑动窗口最大值
Note：使用单调队列

pop(value)：如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作
push(value)：如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止

其实队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的。
那么这个维护元素单调递减的队列就叫做单调队列，即单调递减或单调递增的队列。C++中没有直接支持单调队列，需要我们自己来实现一个单调队列

class Solution {
private:class MyQueue {public:deque<int> que;void pop(int value) {if (!que.empty() && value == que.front())que.pop_front();}void push(int value) {while (!que.empty() && value > que.back())que.pop_back();que.push_back(value);}int front() {return que.front();}};
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {MyQueue que;vector<int> res;for (int i = 0; i < k; i++) {que.push(nums[i]);}res.push_back(que.front());for (int i = k; i < nums.size(); i++) {que.pop(nums[i - k]);que.push(nums[i]);res.push_back(que.front());}return res;}
};

Note：硬滑解题

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {if (nums.empty() || k > nums.size() || k <= 0) {return {};}vector<int> res;int start = 0, end = k - 1;while (end < nums.size()) {int temp = INT_MIN;for (int i = start; i <= end; ++i) {temp = max(temp, nums[i]);}res.push_back(temp);start++; end++;}return res;}
};

二、19. 正则表达式匹配（剑指Offer）

正则表达式匹配

Note：回溯法求解。
1.当s为空串时，此时p为空串，匹配成功
2.当p为空时，此时s不为空，匹配失败
3.如果s和p的第一个字符匹配时，即s[0] == p[0] 或 p[0] == ‘.’时，要对除第一个字符外的s(1)和p(1)递归匹配
4.当p[1] == ‘’时，
如果与其前一个字符匹配s的0个字符时，相当于p少了这两个字符，要递归考虑s和p(2)
如果*与其前一个字符匹配s的k个字符时，相当于s少了这k个字符，而p少了这两个字符，要递归考虑s(k)和p(2)
5.其它情况，匹配失败

class Solution {
public:bool isMatch(string s, string p) {return dfs(s, p);}bool dfs(string s, string p) {if (s.empty()) return p.empty() || p.size() >= 2 && p[1] == '*' && dfs(s, p.substr(2));if (p.empty()) return false;if (s[0] == p[0] || p[0] == '.') {bool r = dfs(s.substr(1), p.substr(1));if (r) return true;}if (!(p.size() >= 2 && p[1] == '*')) return false;bool r = dfs(s, p.substr(2));if (r) return true;for (int c = 0; c < s.size(); c++) {if (s[c] == p[0] || p[0] == '.') {bool r = dfs(s.substr(c + 1), p.substr(2));if (r) return true;}else break;}return false;}
};

Note：动态规划

class Solution {
public:bool isMatch(string s, string p) {int m = s.size() + 1, n = p.size() + 1;//1.确定dp数组//dp[i][j] 代表字符串 s 的前 i 个字符和 p 的前 j 个字符能否匹配vector<vector<bool>> dp(m, vector<bool>(n, false));//2.确定递推公式/*当 p[j - 1] = '*' 时， dp[i][j] 在当以下任一情况为 true 时等于 true：dp[i][j - 2]： 即将字符组合 p[j - 2] * 看作出现 0 次时，能否匹配。dp[i - 1][j] 且 s[i - 1] = p[j - 2]: 即让字符 p[j - 2] 多出现 1 次时，能否匹配。dp[i - 1][j] 且 p[j - 2] = '.': 即让字符 '.' 多出现 1 次时，能否匹配。当 p[j - 1] != '*' 时， dp[i][j] 在当以下任一情况为 true 时等于 true：dp[i - 1][j - 1] 且 s[i - 1] = p[j - 1]： 即让字符 p[j - 1] 多出现一次时，能否匹配。dp[i - 1][j - 1] 且 p[j - 1] = '.'： 即将字符 . 看作字符 s[i - 1] 时，能否匹配。*///3.确定数组初始化dp[0][0] = true;//4.确定遍历顺序for(int j = 2; j < n; j += 2)dp[0][j] = dp[0][j - 2] && p[j - 1] == '*';for(int i = 1; i < m; i++) {for(int j = 1; j < n; j++) {dp[i][j] = p[j - 1] == '*' ?dp[i][j - 2] || dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'):dp[i - 1][j - 1] && (p[j - 1] == '.' || s[i - 1] == p[j - 1]);}}//5.确定输出结果return dp[m - 1][n - 1];}
};

总结

祝大家都能学有所成，找到一份好工作！