【前缀和】【分类讨论】【二分查找】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++**实现。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/229133.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Pandas数据可视化

pandas库是Python数据分析的核心库 它不仅可以加载和转换数据&#xff0c;还可以做更多的事情&#xff1a;它还可以可视化 pandas绘图API简单易用&#xff0c;是pandas流行的重要原因之一 Pandas 单变量可视化 单变量可视化&#xff0c; 包括条形图、折线图、直方图、饼图等 …

精确率(Precision,P),召回率(Recall,R)以及F1值(F1-score,F1)

狗狗识别系统的例子&#xff1a; 假设我们有两个集合&#xff1a; 实际狗狗的集合&#xff08;实际真正是狗狗的图片&#xff09;&#xff1a;A我们识别为狗狗的集合&#xff08;我们认为是狗狗的图片&#xff09;&#xff1a;B 精确率&#xff08;Precision&#xff0c;P&am…

Codeium在IDEA里的3个坑

转载自Codeium在IDEA里的3个坑&#xff1a;无法log in&#xff0c;downloading language server和中文乱码_downloading codeium language server...-CSDN博客文章浏览阅读1.7w次&#xff0c;点赞26次&#xff0c;收藏47次。Codeium安装IDEA插件的3个常见坑_downloading codeiu…

一文初识Linux进程(超详细!)

&#x1f3ac;慕斯主页&#xff1a;修仙—别有洞天 ♈️今日夜电波&#xff1a;HEART BEAT—YOASOBI 2:20━━━━━━️&#x1f49f;──────── 5:35 &#x1f504; ◀️ ⏸ ▶️ ☰ …

Linux实战:部署基于Postfix 与 Dovecot 的邮件系统

一、电子邮件系统简介 在电子邮件系统中&#xff0c;为用户收发邮件的服务器名为邮件用户代理&#xff08;Mail User Agent&#xff0c;MUA&#xff09;&#xff0c;MTA &#xff08;邮件传输代理&#xff09;的工作职责是转发处理不同电子邮件服务供应商之间的邮件&#xff0…

Java EE Servlet之Cookie 和 Session

文章目录 1. Cookie 和 Session1.1 Cookie1.2 理解会话机制 (Session)1.2.1 核心方法 2. 用户登录2.1 准备工作2.2 登录页面2.3 写一个 Servlet 处理上述登录请求2.4 实现登录后的主页 3. 总结 1. Cookie 和 Session 1.1 Cookie cookie 是 http 请求 header 中的一个属性 浏…

网络交换机端口管理会面临的问题

交换机端口管理是跟踪网络交换机及其端口连接详细信息的过程&#xff0c;在大型网络中&#xff0c;交换机端口管理过程通常使用自动化交换机端口管理工具执行。 通过网络交换机端口提供的完全控制和可见性使交换机端口管理工具在管理网络时必不可少&#xff0c;在网络中部署交…

【SpringCloud】从实际业务问题出发去分析Eureka-Server端源码

文章目录 前言1.EnableEurekaServer2.初始化缓存3.jersey应用程序构建3.1注册jeseryFilter3.2构建JerseyApplication 4.处理注册请求5.registry&#xff08;&#xff09; 前言 前段时间遇到了一个业务问题就是k8s滚动发布Eureka微服务的过程中接口会有很多告警&#xff0c;当时…

Halcon闭运算closing

Halcon闭运算 文章目录 Halcon闭运算 闭运算的计算步骤&#xff0c;为先膨胀&#xff0c;后腐蚀。这两步操作能将看起来很接近的元素&#xff0c;如区域内部的空洞或外部孤立的点连接成一体&#xff0c;区域的外观和面积也不会有明显的改变。通俗地说&#xff0c;就是类似于“填…

解决Hive在DataGrip 中注释乱码问题

注释属于元数据的一部分&#xff0c;同样存储在mysql的metastore库中&#xff0c;如果metastore库的字符集不支持中文&#xff0c;就会导致中文显示乱码。 不建议修改Hive元数据库的编码&#xff0c;此处我们在metastore中找存储注释的表&#xff0c;找到表中存储注释的字段&a…

听GPT 讲Rust源代码--library/alloc(2)

File: rust/library/alloc/src/vec/mod.rs 在Rust源代码中&#xff0c;rust/library/alloc/src/vec/mod.rs这个文件是Rust标准库中的Vec类型的实现文件。Vec是一个动态大小的数组类型&#xff0c;在内存中以连续的方式存储其元素。 具体来说&#xff0c;mod.rs文件中定义了以下…

【网络面试(5)】收发数据及断开服务器(四次挥手)

前面了解到服务器和客户端在创建套接字&#xff0c;建立连接后&#xff0c;就可以进入到下一步&#xff0c;双发可以互相发送和接收数据&#xff0c;本篇博客就来学习一下这个过程。  我们印象里&#xff0c;发送数据应该是我们在浏览器输入网址&#xff0c;敲击回车的一瞬间&…

【Python】ubuntu python>3.9编译安装,及多个Python版本并存的使用方法

【Python】ubuntu python3.9编译安装&#xff0c;及多个Python版本并存的使用方法 1. 安装依赖2. 编译与安装2.1 依赖与源获取2.2 配置2.3 编译2.4 安装2.5 建立软连接 链接动态库 3. 多版本兼容 1. 安装依赖 更新系统软件 在正式开始之前&#xff0c;建议首先检查系统软件是否…

FairGuard游戏加固产品常见问题解答

针对日常对接中&#xff0c;各位用户对FairGuard游戏加固方案在安全性、稳定性、易用性、接入流程等方面的关注&#xff0c;我们梳理了相关问题与解答&#xff0c;希望可以让您对产品有一个初步的认知与认可。 Q1:FairGuard游戏加固产品都有哪些功能? A&#xff1a;FairGuar…

VSCode + vite + vue3断点调试配置

没想到这个配置我搞了一上午&#xff0c;网上很多的配置方案都没有效果。总算搞定了&#xff0c;特此记录一下。 首先需要在.vscode文件夹下面创建launch.json配置文件。然后输入如下配置&#xff1a; {// 使用 IntelliSense 了解相关属性。 // 悬停以查看现有属性的描述。//…

【AIGC-图片生成视频系列-5】I2V-Adapter:一种用于视频扩散模型的通用图像生成视频适配器

目录 一. 项目与贡献概述 二. 方法详解 a. 整体框架图 b. 帧相似性先验 三. 一般化图像生成动画结果 四. 基于个性化 T2I 模型的动画结果 五. 结合ControlNet动画结果 六. 项目论文和代码 七. 个人思考与总结 在快速发展的数字内容生成领域&#xff0c;焦点已从文本到…

思福迪运维安全管理系统 test_qrcode_b RCE漏洞复现

产品简介 思福迪运维安全管理系统是思福迪开发的一款运维安全管理堡垒机 漏洞描述 由于思福迪运维安全管理系统 test_qrcode_b路由存在命令执行漏洞&#xff0c;攻击者可通过该漏洞在服务器端任意执行代码&#xff0c;写入后门&#xff0c;获取服务器权限&#xff0c;进而控…

利用Pandas进行高效网络数据获取

利用Pandas进行高效网络数据获取 背景&#xff1a; ​ 最近看到一篇关于使用Pandas模块进行爬虫的文章&#xff0c;觉得很有趣&#xff0c;这里为大家详细说明。 基础铺垫&#xff1a; ​ pd.read_html pandas 库中的一个函数&#xff0c;用于从 HTML 页面中读取表格数据并…

【G-LAB】郭主任的Linux免费公开课~又要开始啦!

带你一起走进Linux的世界&#xff01; 【G-LAB】 Linux最新技术—免费公开课即将开讲&#xff01; 无论是想学习红帽RHEL9.0新特性还是Ansible、容器相关内容&#xff0c; 这个公开课都是你不容错过的&#xff01; ** 公开课课程为期两天&#xff0c;1月4日&#xff06;1月…

单片机开发--keil5

一.keil5 Keil uVision5是一个集成开发环境&#xff08;IDE&#xff09;&#xff0c;用于对嵌入式系统中的微控制器进行编程。它是一个软件套件&#xff0c;包括源代码编辑器、项目经理、调试器以及微控制器开发、调试和编程所需的其他工具。Keil uVision5 IDE主要用于对基于A…