文章目录
- 1. 小美剪彩带
- 2. 最多修改两个字符,生成字典序最小的回文串
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又++了,需要减去1
ans = 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,则两个都改为a
s[idxs[0]] = 'a';
s[n - 1 - idxs[0]] = 'a';
}
else {
// 如果只有一个为a,则修改不是a的那个
// 如果当前串为奇数,还要修改中间位置的为a
s[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;
}