【动态规划】【滑动窗口】C++算法：3003 执行操作后的最大分割数量

作者推荐

【动态规划】【字符串】扰乱字符串

本文涉及的基础知识点

C++算法：滑动窗口总结
动态规划

LeetCode3003 执行操作后的最大分割数量

给你一个下标从 0 开始的字符串 s 和一个整数 k。
你需要执行以下分割操作，直到字符串 s 变为 空：
选择 s 的最长前缀，该前缀最多包含 k 个 不同 字符。
删除 这个前缀，并将分割数量加一。如果有剩余字符，它们在 s 中保持原来的顺序。
执行操作之 前 ，你可以将 s 中 至多一处 下标的对应字符更改为另一个小写英文字母。
在最优选择情形下改变至多一处下标对应字符后，用整数表示并返回操作结束时得到的最大分割数量。
示例 1：
输入：s = “accca”, k = 2
输出：3
解释：在此示例中，为了最大化得到的分割数量，可以将 s[2] 改为 ‘b’。
s 变为 “acbca”。
按照以下方式执行操作，直到 s 变为空：

  • 选择最长且至多包含 2 个不同字符的前缀，“acbca”。
  • 删除该前缀，s 变为 “bca”。现在分割数量为 1。
  • 选择最长且至多包含 2 个不同字符的前缀，“bca”。
  • 删除该前缀，s 变为 “a”。现在分割数量为 2。
  • 选择最长且至多包含 2 个不同字符的前缀，“a”。
  • 删除该前缀，s 变为空。现在分割数量为 3。
    因此，答案是 3。
    可以证明，分割数量不可能超过 3。
    示例 2：
    输入：s = “aabaab”, k = 3
    输出：1
    解释：在此示例中，为了最大化得到的分割数量，可以保持 s 不变。
    按照以下方式执行操作，直到 s 变为空：
  • 选择最长且至多包含 3 个不同字符的前缀，“aabaab”。
  • 删除该前缀，s 变为空。现在分割数量为 1。
    因此，答案是 1。
    可以证明，分割数量不可能超过 1。
    示例 3：
    输入：s = “xxyz”, k = 1
    输出：4
    解释：在此示例中，为了最大化得到的分割数量，可以将 s[1] 改为 ‘a’。
    s 变为 “xayz”。
    按照以下方式执行操作，直到 s 变为空：
  • 选择最长且至多包含 1 个不同字符的前缀，“xayz”。
  • 删除该前缀，s 变为 “ayz”。现在分割数量为 1。
  • 选择最长且至多包含 1 个不同字符的前缀，“ayz”。
  • 删除该前缀，s 变为 “yz”，现在分割数量为 2。
  • 选择最长且至多包含 1 个不同字符的前缀，“yz”。
  • 删除该前缀，s 变为 “z”。现在分割数量为 3。
  • 选择最且至多包含 1 个不同字符的前缀，“z”。
  • 删除该前缀，s 变为空。现在分割数量为 4。
    因此，答案是 4。
    可以证明，分割数量不可能超过 4。
    参数范围：
    1 <= s.length <= 104
    s 只包含小写英文字母。
    1 <= k <= 26

分析

变量解析

dpNotChangedpNotChange[i]表示子串s[i,m_c)的最大分割数
vSplitvSplit[inx][i]=j表示：将s[i]修改成’a’+inx，其它字符不变的情况下，s[i，m_c)的最长前缀是s[i,j)

不修改任何字符的情况下，s拆分成m个子串，分别为[li1,ri1),[li2,ri2)… [lim,rim)。
显然 li1等于0,rim等于m_c， ri1等于li2…
分以下情况:

  • 一，没有改变任何字符。
  • 二，改变某个字后,[lix,rix)发生改变，变成[lix,nix)，只需要考虑nix < rix，原因见下文证明一。

情况二：
分两层循环：

  • 第一层循环：枚举不修改字符的子串。
  • 第二层循环：枚举nix。

两层循环的时间复杂度为：O(s.length)。
枚举nix的时候，分两种情况：
一，s[nix]没有改变，s[nix,m_c)的最大分割数就是dpNotChange[rix]。前提条件是：

  • k<26 否则无论变成k+1。
  • 包括nix，目前已经有k个不同字符
  • [lix,nix]至少有k+1个字符，由于其只有k个不同字符，所以至少有两个字符相同，去掉nix，[lix,nix)至少还有一个相同字符，将其改成k个字符以外的字符。只能证明[lix,rix]有k+1个字符，不能证明是第一个rix。假定第一个rix是rix1，rix会被rix1淘汰，所以不会造成错误。原因见证明一。
    二，枚举s[nix]改成’a’到’z’。通过vSplit查询第一个前缀。

通过滑动窗口计算vSplit[inx][i-1]

s[i,rightk] 共有k个字符，rightk取最小值；是s[i,rightk1]共有k+1个字符，rightk1取最小值。如果没有足够的字符取m_c。
countk 记录了这k个字符，countk1记录了k+1个字符。

countk 包括inx+‘a’countk1的数量为k+1结果为：rightk1
countk 包括inx+‘a’countk1的数量不够k+1结果为：m_c
countk 不包括inx+‘a’countk的数量为k结果为：rightk
countk 不包括inx+‘a’countk的数量不够k结果为：m_c

证明一 i1<=12则dpNotChange[i1] >= dpNotChange[i2]

特殊情况一：如果s[i1,m_c)和s[i2,m_c) 都不到k+1个字符。则两者都为1。
特殊情况二：s[i2,m_c) 不到k+1个字符，s[i1,m_c)有k+1个字符，则前者为1，后者超过1。
s[i1,m_c) 不到k+1个字符，s[i2,m_c)有k+1个字符，这种i情况不存在。
如果两者都有k+1字符
则s[i2,m_c)可以拆分s[i2,i4)和s[i4,m_c)
s[i1,m_c)可以拆分成s[i1,i3)和s[i3,m_c)
则i3<=i4，i1变i3变大;i2变i4，每次迭代i1和i2都变大，若干次后一定会变成特殊情况一或特殊情况二。
假定i3>i4
s[i2,i4]刚好k+1个字符，那么s[i1,i2)+s[i2,i4]+s(i4+i3)的字符数大于等于k+1,这三个子串加在一起就是s[i1,i3)，与s[i1,i3)只有k个字符矛盾。

代码

核心代码

template<class KEY>
class CKeyCount
{
public:
	void Add(const KEY& key, int iCount)
	{
		Cnt[key] += iCount;
		if (0 == Cnt[key])
		{
			Cnt.erase(key);
		}
	}
	std::unordered_map<KEY, int> Cnt;
};

class Solution {
public:
	int maxPartitionsAfterOperations(string s, int k) {
		m_c = s.length();
		vSplit[inx][i]=j表示：将s[i]修改成'a'+inx，其它字符不变的情况下，s[i，m_c)的最长前缀是s[i,j)
		vector<vector<int>> vSplit(26,vector<int>(m_c, m_c));		
		for (int inx = 0; inx < 26; inx++)
		{			
			CKeyCount<char> countk1,countk;	
			//s[i,rightk] 共有k个字符，rightk取最小值；是s[i,rightk1]共有k+1个字符，rightk取最小值。如果没有足够的字符取m_c
			for (int i =1, rightk1 =i-1,rightk=i-1; i < m_c;i++ )
			{	//s(left,right]和inx+'a' 刚好k+1
				while ((rightk +1 < m_c)&&(countk.Cnt.size() < k ))
				{
					countk.Add(s[++rightk],1);
				}
				while ((rightk1 + 1 < m_c) && (countk1.Cnt.size() <= k))
				{
					countk1.Add(s[++rightk1], 1);
				}
				if (countk.Cnt.count('a' + inx))
				{
					vSplit[inx][i - 1] = (k + 1 == countk1.Cnt.size()) ? rightk1 : m_c;
				}
				else
				{
					vSplit[inx][i - 1] = (k  == countk.Cnt.size()) ? rightk : m_c;
				}
				countk.Add(s[i], -1);
				countk1.Add(s[i], -1);
			}
		}

		vector<int> dpNotChange(m_c + 1, 0);//dp1[i]=x表示 ，在不修改的情况下 s[i,m_c)最多可以分割x次
		for (int i = m_c - 1; i >= 0; i--)
		{
			int inx = vSplit[s[i]-'a'][i];
			dpNotChange[i] =  dpNotChange[inx] + 1;
		}
		int iRet = dpNotChange.front();
		int iPreNum = 0;
		for (int i = 0; i < m_c; i = vSplit[s[i]-'a'][i])
		{
			iPreNum++;
			set<char> setHas;
			for (int j = i; j < vSplit[s[i] - 'a'][i]; j++)
			{
				if (setHas.size()==k)
				{
					for (char ch = 'a'; ch <= 'z'; ch++)
					{//修改了j，且s[j]是新的子串的开始
						if (!setHas.count(ch))
						{
							const int inx = vSplit[ch - 'a'][j];
							iRet = max(iRet, iPreNum + 1 + dpNotChange[inx]);
						}
					}
				}				
				setHas.emplace(s[j]);
				if ((setHas.size() == k)&&(k< 26)&&(j-i+1 > k  ))
				{
					iRet = max(iRet, iPreNum + dpNotChange[j]);
				}
			}
		}
		return iRet;
	}
	int m_c;
};

测试用例

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;
	int k;

	
	{
		Solution sln;
		s = "baac", k = 3;
		auto res = sln.maxPartitionsAfterOperations(s, k);
		Assert(2, res);
	}
	{
		Solution sln;
		s = "accca", k = 2;
		auto res = sln.maxPartitionsAfterOperations(s, k);
		Assert(3, res);
	}
	{
		Solution sln;
		s = "aabaab", k = 3;
		auto res = sln.maxPartitionsAfterOperations(s, k);
		Assert(1, res);
	}
	
	
	{
		Solution sln;
		s = "xxyz", k = 1;
		auto res = sln.maxPartitionsAfterOperations(s, k);
		Assert(4, res);
	}
}

两个错误代码

都没有考虑s[nix]会修改。

class Solution {
public:
int maxPartitionsAfterOperations(string s, int k) {
m_c = s.length();
vector<vector> vSplit(2, vector(m_c, m_c));
{
CKeyCount count;
for (int i = 0, right = 0; i < m_c; i++)
{
while ((right < m_c) && (count.Cnt.size() <= k))
{
count.Add(s[right++], 1);
}
vSplit[0][i] = right;
count.Add(s[i], -1);
}
}
{
CKeyCount count;
for (int i = 0, right = 0; i < m_c; i++)
{
while ((right < m_c) && (count.Cnt.size() < k))
{
if ((count.Cnt.size() == k) && (right - i > k))
{
break;
}
count.Add(s[right++], 1);
}
vSplit[1][i] = right;
count.Add(s[i], -1);
}
}
vector<vector> dp(2, vector(m_c+1, 0));
dp[0][0] = 0;
dp[1][1] = -m_c;
for (int i = 0; i < m_c; i++)
{
//没改字符=>没改字符
dp[0][vSplit[0][i]] = max(dp[0][vSplit[0][i]], dp[0][i] + 1);
//没改字符=>改字符
dp[1][vSplit[1][i]] = max(dp[1][vSplit[1][i]], dp[0][i] + 1);
//改字符=>改字符
dp[1][vSplit[0][i]] = max(dp[1][vSplit[0][i]], dp[1][i] + 1);
}
return max(dp[0].back(), dp[1].back());
}
int m_c;
};

class Solution {
public:
int maxPartitionsAfterOperations(string s, int k) {
m_c = s.length();
vector vSplit(m_c, m_c);//vSplit[i]=j表示，在不修改的情况s[i，m_c)的最长前缀是s[i,j)
CKeyCount count;
for (int i = 0, right = 0; i < m_c; i++)
{
while ((right < m_c) && (count.Cnt.size() <= k))
{
count.Add(s[right++], 1);
}
vSplit[i] = right;
count.Add(s[i], -1);
}

	vector<int> dpNotChange(m_c+1, 0);//dp1[i]=x表示 ，在不修改的情况下 s[i,m_c)最多可以分割x次
	for (int i = m_c - 1; i >= 0; i--)
	{
		dpNotChange[i] = max(dpNotChange[i], dpNotChange[vSplit[i]] + 1);
	}
	int iRet = dpNotChange.front();
	int iPreNum = 0;
	for (int i = 0; i < m_c; i = vSplit[i])
	{
		iPreNum++;
		CKeyCount<char> cnt;
		for (int j = i; j < vSplit[i]; j++)
		{
			cnt.Add(s[j], 1);
			if ((cnt.Cnt.size() == k) && (j - i + 1 > k))
			{
				iRet = max(iRet, iPreNum + dpNotChange[j]);
			}
		}
	}
	return iRet;
}
int m_c;

};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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/318116.html

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

相关文章

如何开发测试框架？

如何开发测试框架？

基本概念 库 英文单词叫Library&#xff0c;库是由代码集合成的一个产品&#xff0c;供程序员调用。面向对象的代码组织形成的库叫类库&#xff0c;面向过程的代码组织形成的库叫函数库。 框架 英文单词叫Framework&#xff0c;框架是为解决一个或一类问题而开发的产品&#x…
阅读更多...
【问题探讨】基于非支配排序的蜣螂优化算法NSDBO求解微电网多目标优化调度研究

【问题探讨】基于非支配排序的蜣螂优化算法NSDBO求解微电网多目标优化调度研究

目录 主要内容 模型研究 结果一览 下载链接 主要内容 该模型以环境保护成本和运行成本为双目标构建了微电网优化调度模型&#xff0c;模型目标函数和约束条件复现文献《基于改进粒子群算法的微电网多目标优化调度》&#xff0c;程序的特点是采用非支配排序的蜣螂…
阅读更多...
Flutter-Web从0到部署上线(实践+埋坑)

Flutter-Web从0到部署上线(实践+埋坑)

本文字数&#xff1a;7743字 预计阅读时间&#xff1a;60分钟 01 前言 首先说明一下&#xff0c;这篇文章是给具备Flutter开发经验的客户端同学看的。Flutter 的诞生虽然来自 Google 的 Chrome 团队&#xff0c;但大家都知道 Flutter 最先支持的平台是 Android 和 iOS&#xff…
阅读更多...
挖种子小游戏

挖种子小游戏

欢迎来到程序小院 挖种子 玩法&#xff1a;看到种子点击鼠标左键进行挖种子&#xff0c;30秒内看你能够挖多少颗种子&#xff0c;快去挖种子吧^^。开始游戏https://www.ormcc.com/play/gameStart/251 html <canvas id"canvas" width"640" height"…
阅读更多...
Docker五部曲之三：镜像构建

Docker五部曲之三：镜像构建

文章目录 前言Docker构建架构构建指令构建上下文本地目录Git存储库压缩文件纯文本文件.dockerignore文件 Dockerfile解析器指令环境变量命令执行格式exec格式shell格式 FROMRUNCMDLABELEXPOSEENVADDCOPYENTRYPOINTVOLUMEUSERWORKDIRARGONBUILDSHELL 多级构建 前言 本文均翻译自…
阅读更多...
每日一题——LeetCode1103.分糖果 ||

每日一题——LeetCode1103.分糖果 ||

方法一 个人方法&#xff1a; 有多少人就创建多大的数组并把数组的所有元素初始化为0&#xff0c;只要还有糖果&#xff0c;就循环给数组从头到尾添加糖果&#xff0c;每次分的糖果数递增1&#xff0c;最后可能刚好分完也可能不够&#xff0c;不够就还剩多少给多少。 var dis…
阅读更多...
11Spring IoC注解式开发(下)(负责注入的注解/全注解开发)

11Spring IoC注解式开发(下)(负责注入的注解/全注解开发)

1负责注入的注解 负责注入的注解&#xff0c;常见的包括四个&#xff1a; ValueAutowiredQualifierResource 1.1 Value 当属性的类型是简单类型时&#xff0c;可以使用Value注解进行注入。Value注解可以出现在属性上、setter方法上、以及构造方法的形参上, 方便起见,一般直…
阅读更多...
【 ATU 随笔记 - Inverter 】PV Inverter 太阳能逆变器市场分析

【 ATU 随笔记 - Inverter 】PV Inverter 太阳能逆变器市场分析

一、简介 在上一篇的介绍中与大家分享了Micro Inverter ( 微型逆变器 )的用途与特色&#xff0c;也提到 Micro Inverter 适合家庭或是一些小型企业的需求。太阳能作为再生能源的代表&#xff0c;在当今能源转型中扮演着重要角色&#xff0c;也是有大型企业、大型能源站的需求&a…
阅读更多...
Java项目：06 Springboot的进销存管理系统

Java项目：06 Springboot的进销存管理系统

作者主页&#xff1a;舒克日记 简介&#xff1a;Java领域优质创作者、Java项目、学习资料、技术互助 文中获取源码 进销存管理系统 介绍 进销存系统是为了对企业生产经营中进货、出货、批发销售、付款等全程进行&#xff08;从接获订单合同开 始&#xff0c;进入物料采购、入…
阅读更多...
杨中科 .NETCORE ENTITY FRAMEWORK CORE-1 EFCORE 第一部分

杨中科 .NETCORE ENTITY FRAMEWORK CORE-1 EFCORE 第一部分

一 、什么是EF Core 什么是ORM 1、说明: 本课程需要你有数据库、SOL等基础知识。 2、ORM: ObjectRelational Mapping。让开发者用对象操作的形式操作关系数据库 比如插入: User user new User(Name"admin"Password"123”; orm.Save(user);比如查询: Book b…
阅读更多...
计算机三级（网络技术）一综合题(IP地址计算)

计算机三级（网络技术）一综合题(IP地址计算)

例题一 &#xff08;正常算&#xff09; 计算并填写下表 地址类别 A类地址段是1.0.0.0~127.255.255.255 1~127 B类地址段是128.0.0.0~191.255.255.255 128~191 C类地址段是192.0.0.0~223.255.255.255 192~223 所以41填A 网络地址为主机位全0 根据子网掩码&…
阅读更多...
Redis实现分布式会话

Redis实现分布式会话

Redis实现分布式会话 1 什么是分布式会话 1 这是我么之前学过的注册登录模式 2 如果非常多的人访问&#xff0c;因为单台服务器的访问承受能力是有限的&#xff0c;那么我们就想用多态服务器来承担压力 3 一般通过负载均衡的方式来实现&#xff0c;来分担服务器的压力。 4 负…
阅读更多...
【Redis】Redis数据过期策略、数据淘汰策略

【Redis】Redis数据过期策略、数据淘汰策略

数据过期策略 首先&#xff0c;我们要知道Redis的数据过期策略是惰性删除和定期删除结合使用。 面试题&#xff1a; 惰性删除 定期删除 数据淘汰策略 Redis支持8种数据淘汰策略&#xff1a; noeviction&#xff1a;不淘汰任何key&#xff0c;当内存满时&#xff0c;不写入任何…
阅读更多...
TCP之三次握手四次挥手与UDP区别

TCP之三次握手四次挥手与UDP区别

文章目录 1 TCP三次握手四次挥手1.1 数据包说明1.1.1 TCP数据包1.1.2 UDP数据包1.1.3 TCP和UDP差异1.1.4 TCP可靠性传输机制 1.2 三次握手1.2.1 三次握手定义1.2.2 三次握手问题1.2.2.1 问题引入分析1.2.2.2 历史连接1.2.2.3 同步双方初始序列号1.2.2.4 避免资源浪费 1.3 四次挥…
阅读更多...
POSTGRESQL中ETL、fdw的平行替换

POSTGRESQL中ETL、fdw的平行替换

POSTGRESQL中ETL、fdw的平行替换 01、简介 “ 在我前两次的文章中&#xff0c;说到postgresql对于python的支持&#xff0c;其实很多功能也就可以封装进入的postgresql数据库中去。比如fdw、etl等&#xff0c;本文将以此为叙述点&#xff0c;进行演示展示” 在postgresql数据…
阅读更多...
详解矩阵变换：伸缩，旋转，反射和投影

详解矩阵变换：伸缩，旋转，反射和投影

目录 一. 矩阵子空间 二. 矩阵变换 2.1 伸缩矩阵 2.2 旋转矩阵 2.3 反射矩阵 2.4 投影矩阵 2.5 小结 三. 矩阵变换与函数 3.1 原点 3.2 常数倍性质 3.3 加法性质 3.4 小结 四. 空间变换 五. 小结 一. 矩阵子空间 矩阵与向量相乘Ax可以看成子空间的变换。 零空间…
阅读更多...
一文搞定，JMeter的三种参数化方式

一文搞定，JMeter的三种参数化方式

1、Test Plan 中添加变量 可以在 Test Plan 中设置好添加变量&#xff0c;变量名可以在任意的位置使用&#xff0c;比如说在线程组中直接用${ 变量名 }方式引用&#xff0c;步骤如下&#xff1a; 1&#xff09;设置变量名和变量值 2&#xff09;添加线程组 3&#xff09;添加…
阅读更多...
[情商-11]：人际交流的心理架构与需求层次模型

[情商-11]：人际交流的心理架构与需求层次模型

目录 前言&#xff1a; 一、心理架构 1.1 个体生理层 1.2 个体心理层 1.3 点对点人际交流层 1.4 社会网络层 1.5 社会价值层 二、人的需求层次模型 2.1 需求&#xff08;欲望&#xff09;层次模型 2.2 基因与人需求之间的关系 2.3 个体生理需求 2.4 个体的心理需求…
阅读更多...
MyBatis源码分析（六）：数据源模块

MyBatis源码分析（六）：数据源模块

1. 概述 本文&#xff0c;我们来分享 MyBatis 的数据源模块&#xff0c;对应 datasource 包。如下图所示&#xff1a; ​ 在 MyBatis源码分析&#xff08;二&#xff09;&#xff1a;项目结构 中&#xff0c;简单介绍了这个模块如下&#xff1a; 数据源是实际开发中常用的组件…
阅读更多...
5 微信小程序

5 微信小程序

功能开发 5 功能开发概要今日详细1.发布1.1 发布流程的问题1.2 组件&#xff1a;进度条1.3 修改data中的局部数据1.4 发布示例效果前端后端 1.5 闭包 2.获取前10条新闻&#xff08;动态/心情&#xff0c;无需分页&#xff09;3.复杂版4.文章详细页面 各位小伙伴想要博客相关资料…
阅读更多...
最新文章

Copyright @ 2022~2023