滑動窗口解決字串問題。

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);}
};

加粗樣式

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;}
};

貪心做法：尋找局部最優的邏輯

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;}
};

按代碼隨想錄來說的話，劃分為貪心算法找局部最優的一類問題
今天剛復習了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;}
};