西安手机网站,网页微信版官网登录仅传输文件,西部数码成品网站后台,河南建设建设监理协会网站文章目录1. 小美剪彩带2. 最多修改两个字符#xff0c;生成字典序最小的回文串1. 小美剪彩带 题意#xff1a;找出区间内不超过k种数字子数组的最大长度
使用双指针的方式#xff0c;用哈希表来统计每个数出现次数。在双指针移动的过程中#xff0c;动态的维护区间内不同数…
文章目录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] 区间长度
#includeiostream
#includevector
#includeunordered_mapusing namespace std;int main() {int n, k;cin n k;if (k 0) return 0;vectorint nums(n, 0);for (int i 0; i n; i) cin nums[i];int l 0;int r 0;int ans 0;unordered_mapint, int mp; // val, freqwhile (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;vectorint 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_mapint, 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
cnt0即原字符串就是回文串找到第一个不为a的位置i将i与对称位置n-i-1都改为a
aca --- aaa
acca --- aaaa
acbca --- aabaa cnt1只有一个位置需要修改此时分两种情况 如果 i与对称位置n-i-1都不是a将这俩位置都改为a即可如果 i与对称位置n-i-1只有一个为a将另一个不是a的改为a。此时只改了一个字母还可以改一个。当字符串长度为奇数时将中间字符改为a
abcdba --- abaaba
abcea --- aacaa
cbcac --- caaac cnt2两个对称位置需要修改 i与对称位置n-i-1谁小就改为谁
abcde --- abcbaint main() {string s;cin s;int n s.size();vectorint 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;
}
