微信公众号红包网站开发,wordpress 外网访问 登录路由器,网站建设与网络设计课程,写论文的好网站题目链接#xff1a;https://leetcode.cn/problems/can-make-palindrome-from-substring/description/
题目大意#xff1a;给出一个字符串s#xff0c;每次query给出l, r, k#xff0c;要求判断子串s[l:r1]在经过k次操作后是否能变为回文串。一次操作可以将子串内的一个字…题目链接https://leetcode.cn/problems/can-make-palindrome-from-substring/description/
题目大意给出一个字符串s每次query给出l, r, k要求判断子串s[l:r1]在经过k次操作后是否能变为回文串。一次操作可以将子串内的一个字符变为任意一个其他字符。并且子串顺序可以任意改变。
思路因为有很多query自然想到会有重复计算要检查超时那么就想到前缀和。用pre[j][i]记录到i为止字母j出现的次数。那么子串内字母j出现的次数即为pre[j][r1-l]。
对于子串如果长度为奇数那么回文与否与中间的字符无关我们可以忽略。因此处理的总是一个总长度为偶数的子串。统计子串中每个字母的出现次数可以知道【奇数出现的次数】必然是偶数因为只有偶数个奇数若干偶数才能使得和子串总长度为偶数。
那么对于cnt个出现奇数次的字母我们进行k次操作可以最多让2*k长度的子串变为回文。而对于出现偶数次的字母只需将其对称排列即可。因此判断条件变为cnt / 2 k
完整代码
class Solution {
public:vectorbool canMakePaliQueries(string s, vectorvectorint queries) {int N s.length();int pre[26][10001] {};for (int i 0; i N; i) {int idx s[i]-a;pre[idx][i1] pre[idx][i]1;for (int j 0; j 26; j) {if (j ! idx i 0)pre[j][i1] pre[j][i];}}vectorbool res;for (auto q: queries) {int l q[0], r q[1], k q[2];char mid s[(lr)/2];bool flag (r1-l)%2;int arr[26] {};if (flag)arr[mid-a]--;int cnt 0;for (int j 0; j 26; j) {arr[j] pre[j][r1] - 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();vectorint pre(N1, 0);for (int i 0; i N; i) {pre[i1] pre[i] ^ (1 s[i]-a); }如何统计子串中的字母的奇数的个数呢这就是数一下【代表该区间的二进制数】通过前缀和做差得到中1的个数。 int l q[0], r q[1], k q[2];int cnt 0;int x pre[r1] ^ pre[l];while (x 0) {x x - 1;cnt;}x x-1操作将 x 的二进制表示中最低位的 1 翻转成 0并将所有更低位的位都清零。这是一个位运算技巧快速计算二进制数中1的个数。
另外由于乘法比除法更加快速我们就不考虑是否忽略子串最中间的字母了即使它使得x中1的个数增加了也只不过增加1而已我们将能够处理的上限改为2*k1即可。 if (cnt 2*k1)res.emplace_back(true);elseres.emplace_back(false);完整代码
class Solution {
public:vectorbool canMakePaliQueries(string s, vectorvectorint queries) {int N s.length();vectorint pre(N1, 0);for (int i 0; i N; i) {pre[i1] pre[i] ^ (1 s[i]-a); }vectorbool res;for (auto q: queries) {int l q[0], r q[1], k q[2];int cnt 0;int x pre[r1] ^ pre[l];while (x 0) {x x - 1;cnt;}if (cnt 2*k1)res.emplace_back(true);elseres.emplace_back(false);}return res;}
};
