【位运算】【前缀和】个人练习-Leetcode-1177. Can Make Palindrome from Substring

题目链接：http://leetcode.cn/problems/can-make-palindrome-from-substring/description/

题目大意：给出一个字符串s，每次query给出l, r, k，要求判断子串s[l:r+1]在经过k次操作后是否能变为回文串。一次操作可以将子串内的一个字符变为任意一个其他字符。并且子串顺序可以任意改变。

思路：因为有很多query，自然想到会有重复计算，要检查超时，那么就想到前缀和。用pre[j][i]记录到i为止字母j出现的次数。那么子串内字母j出现的次数即为pre[j][r+1-l]。

对于子串，如果长度为奇数，那么回文与否与中间的字符无关，我们可以忽略。因此处理的总是一个总长度为偶数的子串。统计子串中每个字母的出现次数，可以知道，【奇数出现的次数】必然是偶数，因为只有偶数个奇数+若干偶数才能使得和（子串总长度）为偶数。

那么对于cnt个出现奇数次的字母，我们进行k次操作可以最多让2*k长度的子串变为回文。而对于出现偶数次的字母，只需将其对称排列即可。因此判断条件变为cnt / 2 <= k

完整代码

class Solution {
public:
vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {
int N = s.length();
int pre[26][10001] = {};
for (int i = 0; i < N; i++) {
int idx = s[i]-'a';
pre[idx][i+1] = pre[idx][i]+1;
for (int j = 0; j < 26; j++) {
if (j != idx && i > 0)
pre[j][i+1] = pre[j][i];
}
}
vector<bool> res;
for (auto q: queries) {
int l = q[0], r = q[1], k = q[2];
char mid = s[(l+r)/2];
bool flag = (r+1-l)%2;
int arr[26] = {};
if (flag)
arr[mid-'a']--;
int cnt = 0;
for (int j = 0; j < 26; j++) {
arr[j] += pre[j][r+1] - pre[j][l];
if (arr[j] & 1 == 1) {
cnt++;
}
}
if (cnt / 2 <= k) {
res.emplace_back(true);
}
else {
res.emplace_back(false);
}
}
return res;
}
};

然而，碰到大的测试样例的时候会超时…那么就不得不求助高效的位运算了。

我们用一个二进制数组存储前缀和，每个二进制数一共26位，代表某个字母在i位置前的奇偶性。奇偶性运算用异或操作^来实现。

        int N = s.length();
vector<int> pre(N+1, 0);
for (int i = 0; i < N; i++) {
pre[i+1] = pre[i] ^ (1 << s[i]-'a');            
}

如何统计子串中的字母的奇数的个数呢？这就是数一下【代表该区间的二进制数】（通过前缀和做差得到）中1的个数。

            int l = q[0], r = q[1], k = q[2];
int cnt = 0;
int x = pre[r+1] ^ pre[l];
while (x > 0) {
x &= x - 1;
cnt++;
}

x &= x-1操作将 x 的二进制表示中最低位的 1 翻转成 0，并将所有更低位的位都清零。这是一个位运算技巧，快速计算二进制数中1的个数。

另外，由于乘法比除法更加快速，我们就不考虑是否忽略子串最中间的字母了，即使它使得x中1的个数增加了，也只不过增加1而已，我们将能够处理的上限改为2*k+1即可。

            if (cnt <= 2*k+1)
res.emplace_back(true);
else
res.emplace_back(false);

完整代码

class Solution {
public:
vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {
int N = s.length();
vector<int> pre(N+1, 0);
for (int i = 0; i < N; i++) {
pre[i+1] = pre[i] ^ (1 << s[i]-'a');            
}
vector<bool> res;
for (auto q: queries) {
int l = q[0], r = q[1], k = q[2];
int cnt = 0;
int x = pre[r+1] ^ pre[l];
while (x > 0) {
x &= x - 1;
cnt++;
}
if (cnt <= 2*k+1)
res.emplace_back(true);
else
res.emplace_back(false);
}
return res;
}
};