LeetCode·每日一题·1177. 构建回文串检测·前缀和-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode·每日一题·1177. 构建回文串检测·前缀和。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

作者：小迅
链接：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. 构建回文串检测·前缀和

思路

题意 -> 给定一个字符串，选择其中任意位置 L-R，可以重排任意字符和替换任意 K 个字符，使得 L-R 子串为回文串，能满足要求则为 TRUE，不能则为 FALSE。

要求转换为回文串，什么是回文串呢？形如 abccba 则为回文串，其中存在一个特点为 相同字符为偶数 或者 在前者基础上只有一个字符出现次数为奇数。

那么现在就简单了，题意只关心能否到达要求，不关心其具体字符。那么就可以将给定字符串转换为字符出现次数串，判断一个子串能否转换为回文串 -> 判断将当前位置中字符出现次数是否满足上述要求

那么如何转换到上述题意要求呢？给定一个子串：

相同字符出现的次数如果为偶数的话，那么这个字符就不需要使用修改次数
相同字符出现的次数如果为奇数的话：
- 只有一个字符出现奇数次数，不需要使用修改次数
- 多个字符出现奇数次数的话，需要使用出现次数 / 2 次修改次数，将多余的字符转换为偶数次出现

如何统计每一个位置字符的出现次数呢？

使用数组记录每一个子串的字符出现次数
因为字符只有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模板网！