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

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Couchdb 垂直权限绕过漏洞(CVE-2017-12635)

Couchdb 垂直权限绕过漏洞(CVE-2017-12635)

一、漏洞描述 Apache CouchDB是一个开源数据库&#xff0c;专注于易用性和成为”完全拥抱web的数据库”。它是一个使用JSON作为存储格式&#xff0c;JavaScript作为查询语言&#xff0c;MapReduce和HTTP作为API的NoSQL数据库。应用广泛&#xff0c;如BBC用在其动态内容展示平台…
阅读更多...
YOLOv8训练损失、mAP画图功能 | 支持多结果对比，多结果绘在一个图片（科研必备）

YOLOv8训练损失、mAP画图功能 | 支持多结果对比，多结果绘在一个图片（科研必备）

一、本文介绍 本文给大家带来的是YOLOv8系列的绘图功能&#xff0c;我将向大家介绍YOLO系列的绘图功能。我们在进行实验时&#xff0c;经常需要比较多个结果&#xff0c;针对这一问题&#xff0c;我写了点代码来解决这个问题&#xff0c;它可以根据训练结果绘制损失(loss)和mA…
阅读更多...
QGIS004:【01矢量创建工具箱】-创建网格、从表格创建点图层、导入带有地理标签的照片、点转线

QGIS004:【01矢量创建工具箱】-创建网格、从表格创建点图层、导入带有地理标签的照片、点转线

摘要：QGIS矢量创建工具箱包括创建网格、从表格创建点图层、导入带有地理标签的照片、点转线等选项，本文介绍各选项的基本操作。 实验数据： 链接：https://pan.baidu.com/s/1PcF2ZfE5GM6fFg6rs3GeHA?pwd=rha4 提取码：rha4 一、创建网格 1.网格类型(点） 2.网格类型(线）…
阅读更多...
【Spring实战】15 Logback

【Spring实战】15 Logback

文章目录 1. 依赖2. 配置3. 打印日志4. 启动程序5. 验证6. 调整日志级别7. 代码详细总结 Spring 作为一个现代化的 Java 开发框架&#xff0c;提供了很多便利的功能&#xff0c;其中包括灵活而强大的日志记录。本文将介绍如何结合 Spring 和 Logback 配置和使用日志&#xff0c…
阅读更多...
LM386简易OCL功放电路

LM386简易OCL功放电路

LM386简易OCL功放电路是使用低功耗集成功率放大器LM386构成的OCL功放电路&#xff0c;电路结构简单&#xff0c;容易调试&#xff0c;非常适于自制。 电路工作原理&#xff1a;图中IC1和IC2是两片集成功放LM386&#xff0c;接成OCL电路。C1起到电源滤波及退耦作用&#xff0c;C…
阅读更多...
如何通过使用说明书的优化降低售后支持成本？

如何通过使用说明书的优化降低售后支持成本？

随着市场竞争的加剧&#xff0c;售后服务已成为企业保持竞争优势的关键因素之一。而使用说明书作为产品的重要组成部分&#xff0c;与售后服务之间存在着密切的关系。接下来就探讨一下如何通过优化使用说明书降低售后支持成本&#xff0c;提升售后服务质量。 一、使用说明书对售…
阅读更多...
DevOps系列之 JNI实现Java调用C的实现案例

DevOps系列之 JNI实现Java调用C的实现案例

JNI&#xff08;Java Native Interface&#xff09;允许Java代码与其他语言编写的代码进行交互。以下是一个简单的JNI示例&#xff0c;演示如何使用JNI在Java中调用C/C函数。 最终的目录结构如下&#xff1a; JNI&#xff08;Java Native Interface&#xff09;允许Java代码与其…
阅读更多...
【排序算法】【二叉树】【滑动窗口】LeetCode220: 存在重复元素 III

【排序算法】【二叉树】【滑动窗口】LeetCode220: 存在重复元素 III

作者推荐 【二叉树】【单调双向队列】LeetCode239:滑动窗口最大值 本文涉及的基础知识点 C算法&#xff1a;滑动窗口总结 题目 给你一个整数数组 nums 和两个整数 indexDiff 和 valueDiff 。 找出满足下述条件的下标对 (i, j)&#xff1a; i ! j, abs(i - j) < indexDi…
阅读更多...
如何在2024年编写Android应用程序

如何在2024年编写Android应用程序

如何在2024年编写Android应用程序 本文将介绍以下内容&#xff1a; 针对性能进行优化的单活动多屏幕应用程序 &#x1f92b;&#xff08;没有片段&#xff09;。应用程序架构和模块化 → 每个层面。Jetpack Compose 导航。Firestore。应用程序架构&#xff08;模块化特征驱动…
阅读更多...
BikeDNA（二） OSM数据的内在分析1

BikeDNA（二） OSM数据的内在分析1

BikeDNA&#xff08;二&#xff09; OSM数据的内在分析1 该笔记本分析给定区域的 OSM 自行车基础设施数据的质量。 质量评估是“内在的”&#xff0c;即仅基于一个输入数据集&#xff0c;而不使用外部信息。 对于将 OSM 数据与用户提供的参考数据集进行比较的外在质量评估&…
阅读更多...
多人协同开发git flow，创建初始化项目版本

多人协同开发git flow，创建初始化项目版本

文章目录 多人协同开发git flow&#xff0c;创建初始化项目版本1.gitee创建组织模拟多人协同开发2.git tag 打标签3.git push origin --tags 多人协同开发git flow&#xff0c;创建初始化项目版本 1.gitee创建组织模拟多人协同开发 组织中新建仓库 推送代码到我们组织的仓库 2…
阅读更多...
堆的应用：堆排序和TOP-K问题

堆的应用：堆排序和TOP-K问题

上次才讲完堆的相关问题&#xff1a;二叉树顺序结构与堆的概念及性质&#xff08;c语言实现堆 那今天就接着来进行堆的主要两方面的应用&#xff1a;堆排序和TOP-K问题 文章目录 1.堆排序1.1概念、思路及代码1.2改良代码&#xff08;最初建立大堆用AdjustDow&#xff09; 2. TO…
阅读更多...
2.3 设计FMEA步骤三：功能分析

2.3 设计FMEA步骤三：功能分析

2.3.1 目的 设计功能分析确保要求/规范中的功能适当分配给系统要素。分析必须使用功能术语进行编写。 功能分析地主要目标是： 产品或过程功能可视化。制作功能树/网或功能分析表格和参数图（P图）。展开与顾客（内部和外部）功能相关的要求。将要求或特性与功能关联。促进工…
阅读更多...
测试用例设计方法：正交试验冲锋

测试用例设计方法：正交试验冲锋

1 引言 上篇讲了因果图和判定表法&#xff0c;而这两种方法在变量值很多、排列组合数量极大的场景下&#xff0c;会生成非常庞大且冗余的测试用例&#xff0c;此时我们很难对所有组合场景进行全量测试用例覆盖&#xff0c;基于此短板&#xff0c;正交试验法应运而生。 2 概念及…
阅读更多...
通过国家网络风险管理方法提供安全的网络环境

通过国家网络风险管理方法提供安全的网络环境

印度尼西亚通过讨论网络安全法草案启动了其战略举措。不过&#xff0c;政府和议会尚未就该法案的多项内容达成一致。另一方面&#xff0c;制定战略性、全面的网络安全方法的紧迫性从未像今天这样重要。 其政府官方网站遭受了多起网络攻击&#xff0c;引发了人们对国家网络安全…
阅读更多...
C++系列-附录-windows下安装C++环境

C++系列-附录-windows下安装C++环境

C系列-附录-windows下安装C环境 在线练习&#xff1a; http://noi.openjudge.cn/ https://www.luogu.com.cn/ 参考 Windows搭建C编程环境(VSCodeMingw-w64) C编译器有哪些 MSYS2 介绍、下载与安装、Pacman常用命令 C编译器简介 常见的C编译器 C编译器是将C源代码翻译成可执…
阅读更多...
FingerprintService启动-Android13

FingerprintService启动-Android13

FingerprintService启动-Android13 1、指纹服务启动1.1 rc启动Binder对接指纹厂商TA库1.2 FingerprintService启动1.2.1 SystemServer启动FingerprintService1.2.2 注册Binder服务fingerprint 2、获取底层信息2.1 AIDL 对接TA中获取2.2 指纹类型判断 android13-release 1、指纹…
阅读更多...
PythonStudio=vb7国人写的python可视化窗体设计器IDE，可以替代pyqt designer等设计器了

PythonStudio=vb7国人写的python可视化窗体设计器IDE，可以替代pyqt designer等设计器了

【免费】PythonStudio-1.1.5-x86最新版国人开发的python界面ide&#xff0c;可以制作窗体资源-CSDN文库https://download.csdn.net/download/xiaoyao961/88688447 【免费】PythonStudio-1.1.5-x64-Setup.exe国人开发的python界面ide&#xff0c;可以制作窗体资源-CSDN文库https…
阅读更多...
C# WPF上位机开发（以始为终，寻找真实的上位机需求）

C# WPF上位机开发（以始为终，寻找真实的上位机需求）

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 c# wpf、qt、mfc这些上位机的需求是真实存在的&#xff0c;在现实中有很多应用的地方&#xff0c;这一点大家都很清楚。而程序员本身呢&#xff0c…
阅读更多...
Linux：/proc/sys/vm/目录各文件详解

Linux：/proc/sys/vm/目录各文件详解

目录 前言一、/proc/sys/vm/目录各文件二、相关功能的API函数 前言 /proc/sys/vm/ 目录是 Linux 系统中的一个特殊目录&#xff0c;它包含了与虚拟内存子系统相关的系统内核参数。这些参数可以用来配置系统的虚拟内存管理策略&#xff0c;包括内存分配、页面置换、内存压缩、NU…
阅读更多...
最新文章

Copyright @ 2022~2023