作者：小迅
链接：https://leetcode.cn/problems/can-make-palindrome-from-substring/solutions/2309940/qian-zhui-he-zhu-shi-chao-ji-xiang-xi-by-n3ps/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
题目
思路
题意 -> 给定一个字符串，选择其中任意位置 L-R，可以重排任意字符和替换任意 K 个字符，使得 L-R 子串为 回文串，能满足要求则为 TRUE，不能则为 FALSE。
要求转换为 回文串，什么是回文串呢？形如 abccba 则为回文串，其中存在一个特点为 相同字符为偶数 或者 在前者基础上只有一个字符出现次数为奇数。
那么现在就简单了，题意只关心能否到达要求，不关心其具体字符。那么就可以将给定字符串转换为 字符出现次数串，判断一个子串能否转换为回文串 -> 判断将当前位置中字符出现次数是否满足上述要求
那么如何转换到上述题意要求呢？ 给定一个子串：
- 相同字符出现的次数如果为偶数的话，那么这个字符就不需要使用 修改次数
- 相同字符出现的次数如果为奇数的话：
- 只有一个字符出现奇数次数， 不需要使用 修改次数
- 多个字符出现奇数次数的话， 需要使用 出现次数 / 2 次 修改次数，将多余的字符转换为 偶数次出现
如何统计每一个位置字符的出现次数呢？文章来源：https://www.toymoban.com/news/detail-486249.html
- 使用数组记录每一个子串的字符出现次数
- 因为字符只有26个，那么可以使用一个int型位记录出现次数 0 表示偶数次，1表示奇数次
- 可以使用前缀和，任意位置可以通过左右两个子串状态相差得出当前状态
代码注释超级详细文章来源地址https://www.toymoban.com/news/detail-486249.html
代码
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
bool* canMakePaliQueries(char * s, int** queries, int queriesSize, int* queriesColSize, int* returnSize) {
int n = strlen(s);
int* count = (int*)malloc((n + 1) * sizeof(int));//二进制代替数组
memset(count, 0, (n + 1) * sizeof(int));//初始化
for (int i = 0; i < n; i++) {//前缀和枚举
// ^ 为不带进位的加法
count[i + 1] = count[i] ^ (1 << (s[i] - 'a'));//记录整体状态
}
bool* res = (bool*)malloc(queriesSize * sizeof(bool));//返回值数组
for (int i = 0; i < queriesSize; i++) {//枚举子串
int l = queries[i][0], r = queries[i][1], k = queries[i][2];
//根据上述表示，大于13则可以能满足转换要求
//if (k >= 13) {res[i] = true; continue;}
// 由于没有负值， 那么 0 - 1 等价于 0 + 1
int bits = 0, x = count[r + 1] ^ count[l];//相差得出当前状态
while (x > 0) {//求当奇数出现次数
x &= x - 1;
bits++;
}
res[i] = bits / 2 <= k;//保存有效值
}
*returnSize = queriesSize;
free(count);
return res;
}
作者：小迅
链接：https://leetcode.cn/problems/can-make-palindrome-from-substring/solutions/2309940/qian-zhui-he-zhu-shi-chao-ji-xiang-xi-by-n3ps/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。到了这里，关于LeetCode·每日一题·1177. 构建回文串检测·前缀和的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
