当前位置: 首页 > article >正文

【C++动态规划】有效括号的嵌套深度

本文涉及知识点

C++动态规划

LeetCode1111. 有效括号的嵌套深度

有效括号字符串 定义:对于每个左括号,都能找到与之对应的右括号,反之亦然。详情参见题末「有效括号字符串」部分。
嵌套深度 depth 定义:即有效括号字符串嵌套的层数,depth(A) 表示有效括号字符串 A 的嵌套深度。详情参见题末「嵌套深度」部分。
有效括号字符串类型与对应的嵌套深度计算方法如下图所示:在这里插入图片描述

给你一个「有效括号字符串」 seq,请你将其分成两个不相交的有效括号字符串,A 和 B,并使这两个字符串的深度最小。
不相交:每个 seq[i] 只能分给 A 和 B 二者中的一个,不能既属于 A 也属于 B 。
A 或 B 中的元素在原字符串中可以不连续。
A.length + B.length = seq.length
深度最小:max(depth(A), depth(B)) 的可能取值最小。
划分方案用一个长度为 seq.length 的答案数组 answer 表示,编码规则如下:
answer[i] = 0,seq[i] 分给 A 。
answer[i] = 1,seq[i] 分给 B 。
如果存在多个满足要求的答案,只需返回其中任意 一个 即可。
示例 1:
输入:seq = “(()())”
输出:[0,1,1,1,1,0]
示例 2:
输入:seq = “()(())()”
输出:[0,0,0,1,1,0,1,1]
解释:本示例答案不唯一。
按此输出 A = “()()”, B = “()()”, max(depth(A), depth(B)) = 1,它们的深度最小。
像 [1,1,1,0,0,1,1,1],也是正确结果,其中 A = “()()()”, B = “()”, max(depth(A), depth(B)) = 1 。
提示:
1 < seq.size <= 10000

有效括号字符串:
仅由 “(” 和 “)” 构成的字符串,对于每个左括号,都能找到与之对应的右括号,反之亦然。
下述几种情况同样属于有效括号字符串:

  1. 空字符串

  2. 连接,可以记作 AB(A 与 B 连接),其中 A 和 B 都是有效括号字符串

  3. 嵌套,可以记作 (A),其中 A 是有效括号字符串
    嵌套深度:
    类似地,我们可以定义任意有效括号字符串 s 的 嵌套深度 depth(S):

  4. s 为空时,depth(“”) = 0

  5. s 为 A 与 B 连接时,depth(A + B) = max(depth(A), depth(B)),其中 A 和 B 都是有效括号字符串

  6. s 为嵌套情况,depth(“(” + A + “)”) = 1 + depth(A),其中 A 是有效括号字符串
    例如:“”,“()()”,和 “()(()())” 都是有效括号字符串,嵌套深度分别为 0,1,2,而 “)(” 和 “(()” 都不是有效括号字符串。

简化后的问题:求最小max(a的深度,b的深度)

和本题没直接关系,类似而已。本方法可以求解,只是太麻烦。
如果s[i]为左括号,其权值为1;为右括号,其权值为-1。p[i]记录s[0…i]的权值和。
pa[i]记录s[0…i]中被a选中的权值和。pb[i]记录s[0…i]中被b选中的权值和。
根据括号的等效条件:
条件一, ∀ \forall i,p[i],pa[i],pb[i]都>=0。
条件二:p.back() pa.back() pb.back()都为0。
令f(left,right) 记录s[left…right]中被拆分A,B部分,的最大深度。
推论一:如p[i]等于0,则s[0…i]和s[i+1…n-1]都是合法括号。
推论二:如p[i]等于0,则pa[i]和pb[i]都等于0,即a,b都可以通过s[i]拆分。
推论三:如果s[i] ==0 ,则f(0,n-1) = max(f(0,i),f(i+1,n-1))。
令 11,i2 = g(left,right) 记录s[left…right],i1是A的深度,i2是b的深度。确保max(i1,i2)最小。
推论四:除了p.back()外p[i]全大于0,则
i3,i4 = g(left+1,right-1) , i1 = min(i3,i4)+1 i2 = max(i3,i4)
如果left > right,则返回{0,0}
时间复杂度:O(nn) ∀ \forall i,每层s[i]都只会处理一次。

代码

class Solution {
		public:
			int maxDepthAfterSplit(string seq){
				function<pair<int,int>(int,int)> Do = [&](int left, int right)-> pair<int, int> {
					if (left > right) { return  make_pair(0,0);  }
					int cur = 0;
					for (int i = left; i < right; i++) {
						cur += ('(' == seq[i]) ? 1 : -1;
						if (cur == 0) {							
							auto [i1, i2] = Do(left,i);
							auto [i3, i4] = Do(i+1, right);
							vector<int> is = { i1,i2,i3,i4 };
							sort(is.begin(), is.end());
							return { is[1] ,is.back() };
						}
					}
					auto [i1, i2] = Do(left+1,right-1);
					return { min(i1,i2) + 1,max(i1,i2) };
				};
				auto [i1, i2] = Do(0, seq.length() - 1);
				return max(i1, i2);
			}
		};

单元测试

string seq;
		TEST_METHOD(TestMethod1)
		{
			seq = "(())";
			auto res = Solution().maxDepthAfterSplit(seq);
			AssertEx(1, res);
		}
		TEST_METHOD(TestMethod11)
		{
			seq = "(()())";
			auto res = Solution().maxDepthAfterSplit(seq);
			AssertEx(1, res);
		}
		TEST_METHOD(TestMethod12)
		{
			seq = "()(())()";
			auto res = Solution().maxDepthAfterSplit(seq);
			AssertEx(1, res);
		}

如果用栈判断一个字符串是否是合法括号

左括号入栈。遇到右括号,消掉栈顶的左括号,如果栈为空则非法。最终栈顶应该为空,否则非法。
a,b两个栈分别记录两个子序列,遇到左括号,放到元素少的栈。遇到右括号,消除栈顶元素多的栈。
我们只需要知道栈的元素数量,故可以ca,cb记录两者的数量。
时间复杂度:O(n)

代码

class Solution {
		public:
			vector<int> maxDepthAfterSplit(string seq) {
				int ca = 0,cb=0;
				const int N = seq.length();
				vector<int> ret(N);
				for (int i = 0; i < N;i++ ) {
					if ('(' == seq[i]) {
						if (ca < cb) {
							ca++;
							ret[i] = 0;
						}
						else {
							cb++;
							ret[i] = 1;
						}
					}
					else {
						if (ca > cb) {
							ca--;
							ret[i] = 0;
						}
						else {
							cb--;
							ret[i] = 1;
						}
					}
				}
				return ret;
			}
		};

单元测试

		int MaxDeq(const string& s) {
			int ret = 0,cur=0;
			for (const auto& ch : s)
			{
				cur += ('(' == ch) ? 1 : -1;
				ret = max(ret, cur);
			}
			return ret;
		}
		int Res(const string& s, const vector<int>& res) {
			string s1, s2;
			for (int i = 0; i < s.length(); i++) {
				if (res[i]) {
					s1 += s[i];
				}
				else {
					s2 += s[i];
				}
			}
			return max(MaxDeq(s1), MaxDeq(s2));
		}
		string seq;
		TEST_METHOD(TestMethod1)
		{
			seq = "(())";
			auto res = Solution().maxDepthAfterSplit(seq);
			AssertEx(1, Res(seq, res));
		}
		TEST_METHOD(TestMethod11)
		{
			seq = "(()())";
			auto res = Solution().maxDepthAfterSplit(seq);
			AssertEx(1, Res(seq, res));
		}
		TEST_METHOD(TestMethod12)
		{
			seq = "()(())()";
			auto res = Solution().maxDepthAfterSplit(seq);
			AssertEx(1, Res(seq, res));
		}

扩展阅读

我想对大家说的话
工作中遇到的问题,可以按类别查阅鄙人的算法文章,请点击《算法与数据汇总》。
学习算法:按章节学习《喜缺全书算法册》,大量的题目和测试用例,打包下载。重视操作
有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注
闻缺陷则喜(喜缺)是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛
失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。


http://www.kler.cn/a/373350.html

相关文章:

  • 电科金仓(人大金仓)更新授权文件(致命错误: XX000: License file expired.)
  • 网络搜索引擎Shodan(2)
  • vue3+less使用主题定制(多主题定制)可切换主题
  • 软件测试学习笔记丨SeleniumPO模式
  • 【MyBatis源码】SqlSession实例创建过程
  • 【Searxng】Searxng docker 安装
  • 【Triton 教程】矩阵乘法
  • 新闻列表以及详情页面梳理
  • DAY66WEB 攻防-Java 安全SPEL 表达式SSTI 模版注入XXEJDBCMyBatis 注入
  • Linux find 匹配文件内容
  • 无损将GPT转换为MBR的GDisk操作指南:
  • 数据结构和算法-动态规划(1)-认识动态规划
  • 桥接模式:解耦抽象与实现的利器
  • 【CTF】 文件包含漏洞——data伪协议 【详】
  • win11安装安卓apk原生应用,并设置网络代理
  • 基于MATLAB的地下水模拟系统开发
  • 线性可分支持向量机代码 举例说明 具体的变量数值变化
  • Django+Vue全栈开发项目入门(三)
  • Java面试经典 150 题.P88. 合并两个有序数组(001)
  • Flink CDC系列之:学习理解standalone模式
  • 商品详情接口的应用场景有那些?API接口介绍
  • Jenkins面试整理-如何安装 Jenkins?
  • 房地产网络安全:主要风险及缓解建议
  • 100种算法【Python版】第23篇——A*算法
  • 【综合算法学习】(第十篇)
  • MySQL Workbench安装教程(Windows)