【前缀和】【分类讨论】2983：使用封装类解决回文串重新排列查询

2024-01-03 08:44
文章标签 使用 封装 查询 分类 解决 回文 讨论 前缀 重新排列 2983

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

作者推荐

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

本题同解：

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

本文涉及的基础知识点

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 只包含小写英文字母。

分析

封装类

线段关心

class C2Line
{
public:C2Line(int left1, int right1, int left2, int right2):m_iLeft1(left1), m_iRight1(right1), m_iLeft2(left2), m_iRight2(right2),m_iCrossLeft(max(left1,left2)),m_iCrossRight(min(right1,right2)),m_iUnionLeft(min(left1,left2)),m_iUnionRight(max(right1, right2)), m_bCross(m_iCrossRight >= m_iCrossLeft)		{}	tuple<int, int, int, int> NotCross()const{auto[a, b] = NotCross(m_iLeft1, m_iRight1);auto [c, d] = NotCross(m_iLeft2, m_iRight2);return std::make_tuple(a, b, c, d);}bool IsInclude()const{bool b1 = (m_iLeft1 == m_iUnionLeft) && (m_iRight1 == m_iUnionRight);bool b2 = (m_iLeft2 == m_iUnionLeft) && (m_iRight2 == m_iUnionRight);return b1 || b2;}const int m_iLeft1, m_iRight1, m_iLeft2, m_iRight2;const int m_iCrossLeft, m_iCrossRight, m_iUnionLeft, m_iUnionRight;const bool m_bCross;
protected:tuple<int, int> NotCross(int left, int right)const{if (left == m_iCrossLeft){return std::make_tuple(m_iCrossRight + 1, right);}return std::make_tuple(left,m_iCrossLeft-1);}	
};

前缀和

template<class T = long long >
class CPreSum
{
public:CPreSum(const vector<int>& nums){m_data.push_back(0);for (int i = 0; i < nums.size(); i++){m_data.push_back(m_data[i] + nums[i]);}}template<class _PR>CPreSum(int iSize, _PR pr){m_data.push_back(0);for (int i = 0; i < iSize; i++){m_data.push_back(m_data[i] + pr(i));}}T Sum(int left, int rightExclu)const{return m_data[rightExclu] - m_data[left];}
protected:vector<T> m_data;
};

核心代码

class Solution {
public:vector<bool> canMakePalindromeQueries(string s, vector<vector<int>>& queries) {const int n2 = s.length() / 2;CPreSum<int>* preSumLeft[26],* preSumRight[26];for (int i = 0; i < 26; i++){preSumLeft[i] = new CPreSum<int>(n2, [&](int index) {return s[index] == 'a' + i; });preSumRight[i] = new CPreSum<int>(n2, [&](int index) {return s[n2*2-1-index] == 'a' + i; });}CPreSum<int> preSumNotSame(n2, [&](int index) {return s[index] != s[n2 * 2 - 1 - index]; });auto IsSame = [&](int a, int b){for (int i = 0; i < 26; i++){if (preSumLeft[i]->Sum(a,b+1) != preSumRight[i]->Sum(a,b+1)){return false;}}return true;};		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];C2Line line2(a, b,  c,  d);auto Has = [&](const int a, const int b,const int c,const int d,CPreSum<int>* pPreSum, CPreSum<int>* pPreSumOther){//[a,b]可以任意调整顺序的范围，[c,d]是非交叉范围return pPreSum->Sum(a,b+1) - pPreSumOther->Sum(c,d+1) >= 0;};if (!line2.m_bCross){//两者没有交叉const int iNotSameCount = preSumNotSame.Sum(a, b+1) + preSumNotSame.Sum(c,d+1);vRet.emplace_back(IsSame(a, b) && IsSame(c, d) && (iNotSameCount == preSumNotSame.Sum(0,n2)));}else{if (line2.IsInclude()){vRet.emplace_back(IsSame(line2.m_iUnionLeft, line2.m_iUnionRight) && (preSumNotSame.Sum(line2.m_iUnionLeft, line2.m_iUnionRight +1) == preSumNotSame.Sum(0,n2)));continue;}bool bHas = true;auto [a1, b1, c1, d1] = line2.NotCross();for (int i = 0; i < 26; i++){bHas &= Has(a,b,a1,b1, preSumLeft[i], preSumRight[i]);bHas &= Has(c, d,c1,d1, preSumRight[i], preSumLeft[i]);}vRet.emplace_back(bHas&& IsSame(line2.m_iUnionLeft, line2.m_iUnionRight) && (preSumNotSame.Sum(line2.m_iUnionLeft, line2.m_iUnionRight + 1) == preSumNotSame.Sum(0, n2)));}}return vRet;}
};

测试用例

template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}

template
void Assert(const vector& v1, const vector& 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>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/565123。

相关文章

Java Spring 中 @PostConstruct 注解使用原理及常见场景

Java Spring 中 @PostConstruct 注解使用原理及常见场景

《JavaSpring中@PostConstruct注解使用原理及常见场景》在JavaSpring中,@PostConstruct注解是一个非常实用的功能,它允许开发者在Spring容器完全初... 目录一、@PostConstruct 注解概述二、@PostConstruct 注解的基本使用2.1 基本代
阅读更多...
C#使用StackExchange.Redis实现分布式锁的两种方式介绍

C#使用StackExchange.Redis实现分布式锁的两种方式介绍

《C#使用StackExchange.Redis实现分布式锁的两种方式介绍》分布式锁在集群的架构中发挥着重要的作用,：本文主要介绍C#使用StackExchange.Redis实现分布式锁的... 目录自定义分布式锁获取锁释放锁自动续期StackExchange.Redis分布式锁获取锁释放锁自动续期分布式
阅读更多...
springboot使用Scheduling实现动态增删启停定时任务教程

springboot使用Scheduling实现动态增删启停定时任务教程

《springboot使用Scheduling实现动态增删启停定时任务教程》：本文主要介绍springboot使用Scheduling实现动态增删启停定时任务教程,具有很好的参考价值,希望对大家有... 目录1、配置定时任务需要的线程池2、创建ScheduledFuture的包装类3、注册定时任务，增加、删
阅读更多...
IntelliJ IDEA 中配置 Spring MVC 环境的详细步骤及问题解决

IntelliJ IDEA 中配置 Spring MVC 环境的详细步骤及问题解决

《IntelliJIDEA中配置SpringMVC环境的详细步骤及问题解决》：本文主要介绍IntelliJIDEA中配置SpringMVC环境的详细步骤及问题解决,本文分步骤结合实例给大... 目录步骤 1：创建 Maven Web 项目步骤 2：添加 Spring MVC 依赖1、保存后执行2、将新的依赖
阅读更多...
使用Python实现矢量路径的压缩、解压与可视化

使用Python实现矢量路径的压缩、解压与可视化

《使用Python实现矢量路径的压缩、解压与可视化》在图形设计和Web开发中,矢量路径数据的高效存储与传输至关重要,本文将通过一个Python示例,展示如何将复杂的矢量路径命令序列压缩为JSON格式,... 目录引言核心功能概述1. 路径命令解析2. 路径数据压缩3. 路径数据解压4. 可视化代码实现详解1
阅读更多...
Pandas透视表(Pivot Table)的具体使用

Pandas透视表(Pivot Table)的具体使用

《Pandas透视表(PivotTable)的具体使用》透视表用于在数据分析和处理过程中进行数据重塑和汇总,本文就来介绍一下Pandas透视表(PivotTable)的具体使用,感兴趣的可以了解一下... 目录前言什么是透视表？使用步骤1. 引入必要的库2. 读取数据3. 创建透视表4. 查看透视表总结前言
阅读更多...
Python 交互式可视化的利器Bokeh的使用

Python 交互式可视化的利器Bokeh的使用

《Python交互式可视化的利器Bokeh的使用》Bokeh是一个专注于Web端交互式数据可视化的Python库,本文主要介绍了Python交互式可视化的利器Bokeh的使用,具有一定的参考价值,感... 目录1. Bokeh 简介1.1 为什么选择 Bokeh1.2 安装与环境配置2. Bokeh 基础2
阅读更多...
Android使用ImageView.ScaleType实现图片的缩放与裁剪功能

Android使用ImageView.ScaleType实现图片的缩放与裁剪功能

《Android使用ImageView.ScaleType实现图片的缩放与裁剪功能》ImageView是最常用的控件之一,它用于展示各种类型的图片,为了能够根据需求调整图片的显示效果,Android提... 目录什么是 ImageView.ScaleType？FIT_XYFIT_STARTFIT_CENTE
阅读更多...
Spring 中的循环引用问题解决方法

Spring 中的循环引用问题解决方法

《Spring中的循环引用问题解决方法》：本文主要介绍Spring中的循环引用问题解决方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录什么是循环引用？循环依赖三级缓存解决循环依赖二级缓存三级缓存本章来聊聊Spring 中的循环引用问题该如何解决。这里聊
阅读更多...
MySQL 中的 JSON 查询案例详解

MySQL 中的 JSON 查询案例详解

《MySQL中的JSON查询案例详解》：本文主要介绍MySQL的JSON查询的相关知识,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql 的 jsON 路径格式基本结构路径组件详解特殊语法元素实际示例简单路径复杂路径简写操作符注意MySQL 的 J
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2