【前缀和】【分类讨论】【二分查找】2983：回文串重新排列查询

2024-01-02 09:52
文章标签 查询 分类 二分 查找 回文 讨论 前缀 重新排列 2983

本文主要是介绍【前缀和】【分类讨论】【二分查找】2983：回文串重新排列查询，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

作者推荐

【动态规划】【字符串】C++算法：正则表达式匹配

本文涉及的基础知识点

C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
二分查找算法合集

回文串重新排列查询

给你一个长度为 偶数 n ，下标从 0 开始的字符串 s 。
同时给你一个下标从 0 开始的二维整数数组 queries ，其中 queries[i] = [ai, bi, ci, di] 。
对于每个查询 i ，你需要执行以下操作：
将下标在范围 0 <= ai <= bi < n / 2 内的 子字符串 s[ai:bi] 中的字符重新排列。
将下标在范围 n / 2 <= ci <= di < n 内的 子字符串 s[ci:di] 中的字符重新排列。
对于每个查询，你的任务是判断执行操作后能否让 s 变成一个 回文串 。
每个查询与其他查询都是 独立的 。
请你返回一个下标从 0 开始的数组 answer ，如果第 i 个查询执行操作后，可以将 s 变为一个回文串，那么 answer[i] = true，否则为 false 。
子字符串 指的是一个字符串中一段连续的字符序列。
s[x:y] 表示 s 中从下标 x 到 y 且两个端点 都包含 的子字符串。
示例 1：
输入：s = “abcabc”, queries = [[1,1,3,5],[0,2,5,5]]
输出：[true,true]
解释：这个例子中，有 2 个查询：
第一个查询：

  • a0 = 1, b0 = 1, c0 = 3, d0 = 5
  • 你可以重新排列 s[1:1] => abcabc 和 s[3:5] => abcabc 。
  • 为了让 s 变为回文串，s[3:5] 可以重新排列得到 => abccba 。
  • 现在 s 是一个回文串。所以 answer[0] = true 。
    第二个查询：
  • a1 = 0, b1 = 2, c1 = 5, d1 = 5.
  • 你可以重新排列 s[0:2] => abcabc 和 s[5:5] => abcabc 。
  • 为了让 s 变为回文串，s[0:2] 可以重新排列得到 => cbaabc 。
  • 现在 s 是一个回文串，所以 answer[1] = true 。
    示例 2：

输入：s = “abbcdecbba”, queries = [[0,2,7,9]]
输出：[false]
解释：这个示例中，只有一个查询。
a0 = 0, b0 = 2, c0 = 7, d0 = 9.
你可以重新排列 s[0:2] => abbcdecbba 和 s[7:9] => abbcdecbba 。
无法通过重新排列这些子字符串使 s 变为一个回文串，因为 s[3:6] 不是一个回文串。
所以 answer[0] = false 。
示例 3：
输入：s = “acbcab”, queries = [[1,2,4,5]]
输出：[true]
解释：这个示例中，只有一个查询。
a0 = 1, b0 = 2, c0 = 4, d0 = 5.
你可以重新排列 s[1:2] => acbcab 和 s[4:5] => acbcab 。
为了让 s 变为回文串，s[1:2] 可以重新排列得到 => abccab 。
然后 s[4:5] 重新排列得到 abccba 。
现在 s 是一个回文串，所以 answer[0] = true 。
提示：
2 <= n == s.length <= 105
1 <= queries.length <= 105
queries[i].length == 4
ai == queries[i][0], bi == queries[i][1]
ci == queries[i][2], di == queries[i][3]
0 <= ai <= bi < n / 2
n / 2 <= ci <= di < n
n 是一个偶数。
s 只包含小写英文字母。

前缀和+分类讨论

令s1是s的前半部分，即s[0,n)，s2是s的后半部分颠倒顺序。代码中的a,b和题意中的ab相同。c,d和题意不同，是s2的下标。
c = s.length() - 1 - v[3], d = s.length() - 1 - v[2]。这样s是回文，等同与s1等于s2。

vPreSumLeftvPreSumLeft[i]表示s1中’a’+i 的数量前缀和
vPreSumRightvPreSumRight[i]表示s2中’a’+i 的数量前缀和
IsSame如果s1[a,b]和s2[a,b]中各字符数量相等，返回true，否则返回false
vNotSame记录所有s1[i]!=s2[i]的下标
[iCrossLeft,iCrossRight]表示线段[a,b]和[c,d]相交部分
CanVilidvNotSame[a,b]直接有多少个元素，使用二分查找实现。
线段[iUnion1,iUnion2]包括线段[a,b] [c,d]的最小线段

一维线段的关系

相离：没有交点。
相交分以下情况：

  • 相交部分左都有点，属于一条线段。如:[1,2] [0,3] ，分类为包括。
  • 相交部分左都有点，属于不同的线段，如[1,3],[2,4]，分类为侠义的相交，或者说不包括的相交。
  • 相交部分左边（或右边右点），[1,3] 和[2,3]，分类为包括。
  • 相交部分左右都无点，分类为重合，因为和包括的处理相同。所以当包扩处理。

[a,b]包括[c,d]的判断标准：a等于iUnion1，b等于iUnion2

相离

s1[a,b] 和s2[a,b]的字符数量相等， s1[c,d] 和s2[c,d]的字符数量相等。除[a,b] [c,d]外没有字符不相等。
由于可以任意排列，所以只要字符数量相等，就可以排列成相同。

包括

s1[iUnion1,iUnion2] 和s2[iUnion1,iUnion2]的字符数量相等,除[iUnion1,iUnion2]外，没有字符不等。

侠义相交

针对a,b有两种情况：
a等于iCrossLeft ，这时非重合部分为[iCrossRight+1,b]
b等于iCrossRight,这时非重合部分为[a,iCrossLeft-1]
s1[a,b]中必须有非重合部分的所有的字符，且数量足够。否则无法让s1相等。
c,d类似。

以下几个条件：

  • 一，[a,b]有非重合部分所有字符，[c,d]也是。
  • 二，s1[iUnion1,iUnion2] 和s2[iUnion1,iUnion2]的字符数量相等。
  • 三，除[iUnion1,iUnion2]外，没有字符不等。

代码

核心代码

class Solution {
public:vector<bool> canMakePalindromeQueries(string s, vector<vector<int>>& queries) {const int n2 = s.length() / 2;vector<vector<int>> vPreSumLeft(26, vector<int>(1)), vPreSumRight(26, vector<int>(1));vector<int> vNotSame;for (int i = 0; i < n2; i++){for (int j = 0; j < 26; j++){vPreSumLeft[j].emplace_back(vPreSumLeft[j].back() + (j + 'a' == s[i]));vPreSumRight[j].emplace_back(vPreSumRight[j].back() + (j + 'a' == s[s.length() - 1 - i]));}if (s[i] != s[s.length() - 1 - i]){vNotSame.emplace_back(i);}}auto IsSame = [&](int a, int b){for (int i = 0; i < 26; i++){if (vPreSumLeft[i][b + 1] - vPreSumLeft[i][a] != vPreSumRight[i][b + 1] - vPreSumRight[i][a]){return false;}}return true;};auto NotSameCount = [&](int a, int b){return std::upper_bound(vNotSame.begin(), vNotSame.end(), b) - std::lower_bound(vNotSame.begin(), vNotSame.end(), a);};		vector<bool> vRet;for (const auto& v : queries){const int a = v[0], b = v[1], c = s.length() - 1 - v[3], d = s.length() - 1 - v[2];const int iCrossLeft = max(a, c), iCrossRight = min(b, d);const int iCrossLen = iCrossRight - iCrossLeft + 1;auto Has = [&](const int a, const int b,const vector<int>& vPreSum, const vector<int>& vPreSumOther){//[a,b]可以任意调整顺序的范围，[c,d]是非交叉范围int c = a, d = iCrossLeft-1;if (a == iCrossLeft){c = iCrossRight+1;d = b;}return (vPreSum[b + 1] - vPreSum[a] - (vPreSumOther[d + 1] - vPreSumOther[c])) >= 0;};if (iCrossLen <= 0){//两者没有交叉const int iNotSameCount = NotSameCount(a, b) + NotSameCount(c, d);vRet.emplace_back(IsSame(a, b) && IsSame(c, d) && (iNotSameCount == vNotSame.size()));}else{const int iUnion1 = min(a, c),  iUnion2 = max(b, d);auto IsInclude =[&](const int a, const int b){return (iUnion1 == a) && (iUnion2 == b);};if (IsInclude(a, b) || IsInclude(c, d)){vRet.emplace_back(IsSame(iUnion1, iUnion2) && (NotSameCount(iUnion1, iUnion2) == vNotSame.size() ));continue;}bool bHas = true;for (int i = 0; i < 26; i++){bHas &= Has(a,b, vPreSumLeft[i], vPreSumRight[i]);bHas &= Has(c, d, vPreSumRight[i], vPreSumLeft[i]);}vRet.emplace_back(bHas&& IsSame(iUnion1, iUnion2) && (NotSameCount(iUnion1, iUnion2) == vNotSame.size()));}}return vRet;}
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{assert(t1 == t2);
}template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{if (v1.size() != v2.size()){assert(false);return;}for (int i = 0; i < v1.size(); i++){Assert(v1[i], v2[i]);}
}int main()
{string s, p;vector<vector<int>>queries;{Solution sln;s = "fxdqcfqdxc", queries = { {1,1,7,8},{1,1,5,9},{2,4,8,8},{0,4,6,8},{2,3,7,8},{2,4,5,9},{1,4,9,9} };auto res = sln.canMakePalindromeQueries(s, queries);Assert(vector<bool>{false, true, false, true, false, true, false}, res);}{Solution sln;s = "dbaabd", queries = { {0, 1, 5, 5}, { 1,2,4,5 } };auto res = sln.canMakePalindromeQueries(s, queries);Assert(vector<bool>{true,true}, res);}{Solution sln;s = "ceddceddcc", queries = { {0,1,6,8} };auto res = sln.canMakePalindromeQueries(s, queries);Assert(vector<bool>{false}, res);}{Solution sln;s = "acbcab", queries = { {1,2,4,5} };auto res = sln.canMakePalindromeQueries(s, queries);Assert(vector<bool>{true}, res);}{Solution sln;s = "abbcdecbba", queries = { {0,2,7,9} };auto res = sln.canMakePalindromeQueries(s, queries);Assert(vector<bool>{false}, res);}{Solution sln;s = "abcabc", queries = { {1,1,3,5},{0,2,5,5} };auto res = sln.canMakePalindromeQueries(s, queries);Assert(vector<bool>{true, true}, res);}{Solution sln;s = "odaxusaweuasuoeudxwa", queries = { {0,5,10,14} };auto res = sln.canMakePalindromeQueries(s, queries);Assert(vector<bool>{false}, res);}}

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关

下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 **C+

+17**
如无特殊说明，本算法用**C++**实现。

这篇关于【前缀和】【分类讨论】【二分查找】2983：回文串重新排列查询的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/562093。

相关文章

浅谈mysql的sql_mode可能会限制你的查询

浅谈mysql的sql_mode可能会限制你的查询

《浅谈mysql的sql_mode可能会限制你的查询》本文主要介绍了浅谈mysql的sql_mode可能会限制你的查询,这个问题主要说明的是,我们写的sql查询语句违背了聚合函数groupby的规则... 目录场景：问题描述原因分析：解决方案：第一种：修改后，只有当前生效，若是mysql服务重启，就会失效；
阅读更多...
MySQL多列IN查询的实现

MySQL多列IN查询的实现

《MySQL多列IN查询的实现》多列IN查询是一种强大的筛选工具,它允许通过多字段组合快速过滤数据,本文主要介绍了MySQL多列IN查询的实现,具有一定的参考价值,感兴趣的可以了解一下... 目录一、基础语法：多列 IN 的两种写法1. 直接值列表2. 子查询二、对比传统 OR 的写法三、性能分析与优化1.
阅读更多...
MySQL中闪回功能的方案讨论及实现

MySQL中闪回功能的方案讨论及实现

《MySQL中闪回功能的方案讨论及实现》Oracle有一个闪回（flashback）功能,能够用户恢复误操作的数据,这篇文章主要来和大家讨论一下MySQL中支持闪回功能的方案,有需要的可以了解下... 目录1、 闪回的目标2、 无米无炊一3、 无米无炊二4、 演示5、小结oracle有一个闪回（flashb
阅读更多...
mybatis-plus 实现查询表名动态修改的示例代码

mybatis-plus 实现查询表名动态修改的示例代码

《mybatis-plus实现查询表名动态修改的示例代码》通过MyBatis-Plus实现表名的动态替换,根据配置或入参选择不同的表,本文主要介绍了mybatis-plus实现查询表名动态修改的示... 目录实现数据库初始化依赖包配置读取类设置 myBATis-plus 插件测试通过 mybatis-plu
阅读更多...
MySQL中实现多表查询的操作方法(配sql+实操图+案例巩固 通俗易懂版)

MySQL中实现多表查询的操作方法(配sql+实操图+案例巩固 通俗易懂版)

《MySQL中实现多表查询的操作方法(配sql+实操图+案例巩固通俗易懂版)》本文主要讲解了MySQL中的多表查询,包括子查询、笛卡尔积、自连接、多表查询的实现方法以及多列子查询等,通过实际例子和操... 目录复合查询1. 回顾查询基本操作group by 分组having1. 显示部门号为10的部门名，员
阅读更多...
Windows系统下如何查找JDK的安装路径

Windows系统下如何查找JDK的安装路径

《Windows系统下如何查找JDK的安装路径》：本文主要介绍Windows系统下如何查找JDK的安装路径,文中介绍了三种方法,分别是通过命令行检查、使用verbose选项查找jre目录、以及查看... 目录一、确认是否安装了JDK二、查找路径三、另外一种方式如果很久之前安装了JDK，或者在别人的电脑上，想
阅读更多...
mysql关联查询速度慢的问题及解决

mysql关联查询速度慢的问题及解决

《mysql关联查询速度慢的问题及解决》：本文主要介绍mysql关联查询速度慢的问题及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录mysql关联查询速度慢1. 记录原因1.1 在一次线上的服务中1.2 最终发现2. 解决方案3. 具体操作总结mysql
阅读更多...
mysql线上查询之前要性能调优的技巧及示例

mysql线上查询之前要性能调优的技巧及示例

《mysql线上查询之前要性能调优的技巧及示例》文章介绍了查询优化的几种方法,包括使用索引、避免不必要的列和行、有效的JOIN策略、子查询和派生表的优化、查询提示和优化器提示等,这些方法可以帮助提高数... 目录避免不必要的列和行使用有效的JOIN策略使用子查询和派生表时要小心使用查询提示和优化器提示其他常
阅读更多...
C++实现回文串判断的两种高效方法

C++实现回文串判断的两种高效方法

《C++实现回文串判断的两种高效方法》文章介绍了两种判断回文串的方法：解法一通过创建新字符串来处理,解法二在原字符串上直接筛选判断,两种方法都使用了双指针法,文中通过代码示例讲解的非常详细,需要的朋友... 目录一、问题描述示例二、解法一：将字母数字连接到新的 string思路代码实现代码解释复杂度分析三、
阅读更多...
SQL 中多表查询的常见连接方式详解

SQL 中多表查询的常见连接方式详解

《SQL中多表查询的常见连接方式详解》本文介绍SQL中多表查询的常见连接方式,包括内连接（INNERJOIN）、左连接（LEFTJOIN）、右连接（RIGHTJOIN）、全外连接（FULLOUTER... 目录一、连接类型图表（ASCII 形式）二、前置代码（创建示例表）三、连接方式代码示例1. 内连接（I
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2