76. 最小覆盖子串
滑动窗口解决字串问题。
labuladong的算法小抄中关于滑动窗口的算法总结：
class Solution {
public:string minWindow(string s, string t) {unordered_map<char,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];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;}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);}
};
239. 滑动窗口最大值
加粗样式
class Solution {
public: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();}};vector<int> maxSlidingWindow(vector<int>& nums, int k) {MyQueue que;vector<int> result;for(int i=0;i<k;i++) {que.push(nums[i]);}result.push_back(que.front());for(int i=k;i<nums.size();i++) {que.pop(nums[i-k]);que.push(nums[i]);result.push_back(que.front());}return result;}
};
53. 最大子数组和
贪心做法：寻找局部最优的逻辑
class Solution {
public:int maxSubArray(vector<int>& nums) {if(nums.size()<=1)return nums[0];int sum = nums[0];int res = sum;for(int i=1;i<nums.size();i++) {sum = max(nums[i]+sum , nums[i]);if(sum > res)res = sum;}return res;}
};
56. 合并区间
按代码随想录来说的话，划分为贪心算法找局部最优的一类问题
今天刚复习了STL的vector底层原理，这个back()是已经实现好的函数，能够获取得数组未元素(的引用)
class Solution {
public:static bool cmp(vector<int>& a, vector<int>& b) {if(a[0]==b[0])return a[1]<b[1];elsereturn a[0] < b[0];}vector<vector<int>> merge(vector<vector<int>>& intervals) {if(intervals.size() <=1)return intervals;sort(intervals.begin(),intervals.end(),cmp);vector<vector<int>> res;res.push_back(intervals[0]);for(int i=0;i<intervals.size();i++) {if(intervals[i][0] <= res.back()[1]) {res.back()[1] = max(intervals[i][1], res.back()[1]);}else {res.push_back(intervals[i]);}}return res;}
};
