1. 小美剪彩带

在这里插入图片描述
题意：找出区间内不超过k种数字子数组的最大长度

使用双指针的方式，用哈希表来统计每个数出现次数。在双指针移动的过程中，动态的维护区间内不同数个数。具体的，当右端点遇到一个新的数时map的记录+1，当左端点删去一个只出现一次的数时map的记录-1，在这个过程中统计窗口最大值即可

首先用r指针不断往map中添加数据，直到map中的数据多于k个，此时让mp.size() = k + 1的元素4已经放入了mp，且r又++了（此时元素5还没放入map），不算map中最后放入的那个元素，map正好存放的是存放k种数字的所有元素

即r-1指向让mp.size() = k + 1的元素，r - 2指向最后一个让mp.size() = k的元素，需要计算 [l,r - 2] 区间长度

在这里插入图片描述

map中数据过多后，l指针右移，直到区间内数据不大于k，如此往复直到r越界

当r不断向右移动的过程中，若map没有先满，而是r越界了，此时情况不一样，需要记录的 [l,r - 1] 区间长度
在这里插入图片描述

#include<iostream>
#include<vector>
#include<unordered_map>using namespace std;int main() {int n, k;cin >> n >> k;if (k == 0) return 0;vector<int> nums(n, 0);for (int i = 0; i < n; i++) cin >> nums[i];int l = 0;int r = 0;int ans = 0;unordered_map<int, int> mp;  // <val, freq>while (r < n) {while (r < n && (int)mp.size() <= k) {mp[nums[r]]++;r++;}if ((int)mp.size() > k) {// 如果是因为mp装入太多数了，导致已经大于k了，退出while// 说明让mp.size() = k + 1的nums[r]已经放入了mp，且r又++了，需要减去1ans = max(ans, r - l - 1);}else {// 肯定是因为r == n了，mp.size()依然<=k，[l, r)区间内都是满足的ans = max(ans, r - l);break;}while (l <= r && (int)mp.size() > k) {mp[nums[l]]--;if (mp[nums[l]] == 0) mp.erase(nums[l]);l++;}}cout << ans << endl;return 0;
}

map中始终存放[l,r]区间内的数据，mp.size() <= k时不断右移 r 指针，mp.size()一旦大于k，就需要右移 l 指针

int main() {int n, k;cin >> n >> k;if (k == 0) return 0;vector<int> nums(n, 0);for (int i = 0; i < n; i++) cin >> nums[i];int l = 0;int r = 0;int ans = 0;// <val, freq>// 始终存放[l,r]区间内的数据，mp.size()一旦大于k，就需要移动l指针unordered_map<int, int> mp;  while (r < n) {mp[nums[r]]++;while (mp.size() > k) {mp[nums[l]]--;if (mp[nums[l]] == 0) mp.erase(nums[l]);l++;}ans = max(ans, r - l + 1);r++;}cout << ans << endl;return 0;
}

2. 最多修改两个字符，生成字典序最小的回文串

在这里插入图片描述

在这里插入图片描述
由于字符串经过修改一定为回文串，且最多修改两次，所以原字符串位置i与对称位置n-i-1不一样的个数最多为2。所以统计一下需要改的位置个数，记为cnt

cnt=0，即原字符串就是回文串，找到第一个不为a的位置i，将i与对称位置n-i-1都改为a

aca      ---> aaa
acca     ---> aaaa
acbca    ---> aabaa

cnt=1，只有一个位置需要修改，此时分两种情况
- 如果 i与对称位置n-i-1都不是a，将这俩位置都改为a即可
- 如果 i与对称位置n-i-1只有一个为a，将另一个不是a的改为a。此时只改了一个字母，还可以改一个。当字符串长度为奇数时，将中间字符改为a

abcdba  ---> abaaba
abcea   ---> aacaa
cbcac   ---> caaac

cnt=2，两个对称位置需要修改， i与对称位置n-i-1，谁小就改为谁

abcde  ---> abcba

int main() {string s;cin >> s;int n = s.size();vector<int> idxs;for (int i = 0; i < n / 2; i++) {if (s[i] != s[n - 1 - i]) {idxs.push_back(i);}}int cnt = idxs.size();if (cnt == 0) {// 本身就是回文串，需要找到第一个不是a的地方修改for (int i = 0; i <= n / 2; i++) {if (s[i] != 'a') {s[i] = 'a';s[n - 1 - i] = 'a';break;}}}else if (cnt == 1) {// 只有一个需要修改的地方if (s[idxs[0]] != 'a' && s[n - 1 - idxs[0]] != 'a') {// 如果对称位置都不是a，则两个都改为as[idxs[0]] = 'a';s[n - 1 - idxs[0]] = 'a';}else {// 如果只有一个为a，则修改不是a的那个// 如果当前串为奇数，还要修改中间位置的为as[idxs[0]] = 'a';s[n - 1 - idxs[0]] = 'a';if (n & 1) {s[n / 2] = 'a';}}}else {// 有两个需要修改的地方，当前位置idxs[i]和对称位置n - 1 - idxs[i]，谁小就改为谁for (int i = 0; i < cnt; i++) {char c = min(s[idxs[i]], s[n - 1 - idxs[i]]);s[idxs[i]] = c;s[n - 1 - idxs[i]] = c;}}cout << s << endl;return 0;
}

美团面试手撕题

重叠：矩形重合面积大于0

给出矩形的坐标和权值，如果有矩形重叠了，则删除权值较小的矩形，矩形重叠时若权值相同，则删除靠右的矩形。应保留尽可能多的矩形，使得最终剩下的矩形全都不重叠（如果权值大的矩形和两个权值小的矩形重叠，而两个小矩形不重叠，则应该删除两个权值小的矩形）

首先确定当前矩形中权值最大的矩形肯定不会被删除，用权值最大的矩形和剩下的所有矩形比较，重叠则删除，不重叠则保留。首先将当前权值最大的矩形放到ans中，然后用ans最后一个矩形和其他矩形比较，确定需要保留下来的矩形，然后把保留下来矩形的第一个存入ans，接下来再用ans最后一个矩形和保留下来的矩形比较，再确定需要保留下来的矩形…

判断矩形重叠时，将两个矩形映射到x和y轴上，比较x和y轴上两条线段的关系，不重叠有四种情况，剩下就是重叠的情况

在这里插入图片描述

class Cmp {
public:bool operator()(pair<int, vector<int>> rec1, pair<int, vector<int>> rec2) {if(rec1.first != rec2.first){// 权值降序return rec1.first > rec2.first;}// 左下角的横坐标升序return rec1.second[0] < rec2.second[0];}
};// vector中存放左下和右上的横纵坐标
bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) {if (rec2[0] >= rec1[2] || rec2[2] <= rec1[0]) return false;if (rec2[1] >= rec1[3] || rec2[3] <= rec1[1]) return false;return true;
}// 权值和坐标
vector<pair<int, vector<int>>> fun(vector<pair<int, vector<int>>> Rectangles) {vector<pair<int, vector<int>>> ans;if (Rectangles.empty()) return ans;sort(Rectangles.begin(), Rectangles.end(), Cmp());ans.push_back(Rectangles[0]);Rectangles.erase(Rectangles.begin());while (!Rectangles.empty()) {int n = Rectangles.size();vector<int> save;for (int i = 0; i < n; i++) {if (!isRectangleOverlap((ans.end() - 1)->second, Rectangles[i].second) ){save.push_back(i); // 和ans最后一个不重合，则保留下来}}vector<pair<int, vector<int>>> tmp;for (int i : save) {// tmp存放需要保留下来的矩形tmp.push_back(Rectangles[i]);}tmp.swap(Rectangles);if (!Rectangles.empty()) {ans.push_back(Rectangles[0]);Rectangles.erase(Rectangles.begin());}}return ans;
}