习题练习（滑动队列）-拓冰建站

1、LeetCode 209. 长度最小的子数组

解题思路：滑动队列，有的类似贪心，从头到尾开吃，当吃够了就吐

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {queue<int>tt;int mi = INT_MAX;int sum = 0;for(auto i : nums){sum+=i;tt.push(i);while(sum - tt.front()>=target){sum-=tt.front();tt.pop();}if(tt.size() < mi && sum >= target)mi = tt.size();}return mi == INT_MAX? 0 : mi;}
};

2、LeetCode 3. 无重复字符的最长子串

解题思路：和上面那个题差不多，也是这样，但是遇到重复的就开吐，但是吐前要求最大长度的子串，最后也要求一次

class Solution {
public:int lengthOfLongestSubstring(string s) {unordered_map<char,int>mp;queue<char>qu;int sum = 0;int mx = INT_MIN;for(auto i : s){if(!mp[i]){mp[i]++;sum++;qu.push(i);}else{mx = max(mx,sum);while(!qu.empty() && qu.front() != i){mp.erase(qu.front());qu.pop();sum--;}if(!qu.empty() && qu.front()==i){qu.pop();qu.push(i);}}}mx = max(mx,sum);return mx == INT_MIN ? 0 : mx;}
};

3、LeetCode 76. 最小覆盖子串

解题思路：这个题和之前的题差不多，但是这个题要提前处理好给定的子串，然后先吃，吃到完成之后就在吃的串可以组成给定的串的条件下维护最小的长度可以开始往后吐，直到吃下的串不能组成给定的子串，然后继续吃

class Solution {
public:string minWindow(string s, string t) {unordered_map<char, int> find;   unordered_map<char, int> mp;     queue<int> qu;                    string ans = "";int min_len = INT_MAX;           for (auto c : t) find[c]++;      int left = 0;                     int count = 0;                     for (int right = 0; right < s.size(); right++) {char c = s[right];if (find.count(c)) {           mp[c]++;qu.push(right);            if (mp[c] == find[c])     count++;}while (count == find.size()) {int current_len = right - left + 1;if (current_len < min_len) {min_len = current_len;ans = s.substr(left, current_len);}char left_char = s[left];if (find.count(left_char)) {mp[left_char]--;if (mp[left_char] < find[left_char])count--;}left++;}}return ans;}
};

4、LeetCode 134. 加油站

解题思路：遇到圆，管他三七二十一先化曲为直，然后计算每个点到下一个点的油差也就是gas[i]-cost[i]这就是当前i点的油差，然后用滑动窗口，用一个sum来表示油差，如果和大于等于0就可以到，否则到不了，如果到不了那这一段都不行，sum重新从0开始加

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int n = gas.size();vector<int> c(2 * n);   for (int i = 0; i < n; i++) {c[i] = gas[i] - cost[i];c[i + n] = c[i];     }int sum = 0;     int l = 0;       for (int r = 0; r < 2 * n; r++) {sum += c[r];if (sum < 0) {l = r + 1;sum = 0;}if (r - l + 1 == n) {return l;}}return -1;  }
};

5、Blackboard Game

解题思路：找规律，4的倍数都不行

#include<bits/stdc++.h>
#define endl "\n"
#define ll long long
#define pii pair<int,int>
using namespace std;int main() {int t; cin >> t;while (t--) {int n; cin >> n;if (n % 4 == 0)cout << "Bob" << endl;elsecout << "Alice" << endl;}return 0;
}

6、 Tournament

解题思路：这样想，如果k为1时，只能剩下一个人，所以只有j是最强的或者最强之一才有可能会赢，否则就是输，如果k>1,那么极端情况考虑，所以人都抽不到j，勾命到最后，这个题就结束了

#include<bits/stdc++.h>
#define endl "\n"
#define ll long long
#define pii pair<int,int>
using namespace std;int main() {int t; cin >> t;while (t--) {int n, j, k;cin >> n >> j >> k;int mx = -1;int val = -1;for (int i = 1; i <= n; i++) {int temp; cin >> temp;if (i == j)val = temp;mx = max(mx, temp);}cout << ((k > 1 || mx == val) ? "YES" : "NO") << endl;}return 0;
}

7、Prefix Min and Suffix Max

解题思路：就这个题来说，找最大最小值，头往尾遍历一次，尾往头遍历一次，维护遍历过的最大最小值与当前的值对比就行了