前言
今天早上有点其他事情，就没做这次题目，下午回来想着还是坐下看看，这里记录下本次周赛的第三题。前面两题都相较前几次的简单，就不介绍了，而且感觉第二题的题意不太清楚，还好是没在竞赛，看得到答案，否则我觉得ac不了第二题。直接看下题目：
题意
题意的话我直接贴一张图片就行了：
解析
大致思路是遍历整个的queries，判断其对应的子串能否通过变化变成回文串。
要求很重要*我们可以 重新排列 子串 s[left], …, s[right]，并从中选择 最多 k 项替换成任何小写英文字母。 *还有提示部分有说原本字符串中只有小写字母，这是一个比较重要的条件，后面会用到。
关键的一点是要判断如何使一条子串能否变成回文。因为只有小写字母，再结合回文串的性质，其中最多只有一个字符是单数，其余字符都是双数，因为可以随意变换位置，所以问题转换为求出一个子串中单个字符的个数，根据queries中的k值去比较单个字符串的个数大于（1/2）就是true，否则为false.
但是，这样还是不能ac，会在倒数第二个测试超时，因为没在竞赛，所以我还可以好好思考下，重点来了，因为字符串都是小写字母，所以最多只有26中情况，最多只有26种字符都是单数，所以只要k值大于等于13就一定可以改为回文串。
所以加上这个条件就可以ac了。
还有一点要提，统计其中每个子串种每个字符个数，使用一个基数排序。
ac代码
class Solution {
public:
vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {
int size=queries.size();
vector<bool> ret(size,false);
for(int i=0;i<size;i++){
int left=queries[i][0],right=queries[i][1];
int len=right-left+1;
//string tmp=s.substr(queries[i][0],len);
int flag[26];
memset(flag,0,sizeof(flag));
if(queries[i][2]>=13) {
ret[i]=true;
continue;
}
for(int k=left;k<=right;k++){
flag[s[k]-'a']++;
}
int help=0;
for(int m=0;m<26;m++){
if(flag[m]%2==1) help++;
}
if((help/2)<=queries[i][2]) ret[i]=true;
if(len%2==1 && ((help-1)/2)<=queries[i][2]) ret[i]=true;
}
return ret;
}
};最后注意一下其中的小细节就可以了。
给一个ac截图
可能是因为没在竞赛，没紧张感所以效率高一点吧，要是在竞赛里感觉只能ac两道。