本文主要是介绍【位运算】【前缀和】个人练习-Leetcode-1177. Can Make Palindrome from Substring,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目链接:https://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);elseres.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);elseres.emplace_back(false);}return res;}
};
这篇关于【位运算】【前缀和】个人练习-Leetcode-1177. Can Make Palindrome from Substring的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!