当前位置：首页 > news >正文

【C++前缀和状态压缩】1177. 构建回文串检测|1848

news 2024/9/25 8:04:30

本文涉及的基础知识点

C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例包括课程视频
位运算、状态压缩、枚举子集汇总

LeetCode 1177. 构建回文串检测

难度分：1848
给你一个字符串 s，请你对 s 的子串进行检测。
每次检测，待检子串都可以表示为 queries[i] = [left, right, k]。我们可以重新排列子串 s[left], …, s[right]，并从中选择最多 k 项替换成任何小写英文字母。
如果在上述检测过程中，子串可以变成回文形式的字符串，那么检测结果为 true，否则结果为 false。
返回答案数组 answer[]，其中 answer[i] 是第 i 个待检子串 queries[i] 的检测结果。
注意：在替换时，子串中的每个字母都必须作为独立的项进行计数，也就是说，如果 s[left…right] = “aaa” 且 k = 2，我们只能替换其中的两个字母。（另外，任何检测都不会修改原始字符串 s，可以认为每次检测都是独立的）
示例：
输入：s = “abcda”, queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
输出：[true,false,false,true,true]
解释：
queries[0] : 子串 = “d”，回文。
queries[1] : 子串 = “bc”，不是回文。
queries[2] : 子串 = “abcd”，只替换 1 个字符是变不成回文串的。
queries[3] : 子串 = “abcd”，可以变成回文的 “abba”。也可以变成 “baab”，先重新排序变成 “bacd”，然后把 “cd” 替换为 “ab”。
queries[4] : 子串 = “abcda”，可以变成回文的 “abcba”。
提示：
1 <= s.length, queries.length <= 10⁵
0 <= queries[i][0] <= queries[i][1] < s.length
0 <= queries[i][2] <= s.length
s 中只有小写英文字母

前缀和

令s[left…right]数量为奇数的字符数量为m，如果 m <= 2 $\times$ k + 1 。唯一的奇数字符放到中间。
preSum[i] 记录字符‘a’+1 的数量的前缀和，由于只关注奇偶性，所以偶数统一为0，奇数统一为1。
利用状态压缩将preSum[0…25][j]压缩成p[j]

代码

核心代码

class Solution {public:vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {int iMask = 0;vector<int> vMask(1);for (auto& ch : s){iMask ^= (1 << (ch - 'a'));vMask.push_back(iMask);}vector<bool> vRet;for (auto& v : queries){int iMask = vMask[v[1] + 1] ^ vMask[v[0]];int iBitCnt = bitcount(iMask);vRet.push_back(iBitCnt / 2 <= v[2]);}return vRet;}//通过 x &= (x-1)实现int bitcount(unsigned x) {int countx = 0;while (x) {countx++;x &= (x - 1);}return countx;}};

单元测试

	string s;vector<vector<int>> queries;TEST_METHOD(TestMethod11){s = "abcda", queries = { {3,3,0},{1,2,0},{0,3,1},{0,3,2},{0,4,1} };auto res = Solution().canMakePaliQueries(s, queries);AssertEx({ true,false,false,true,true }, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功