【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

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

空字符串
连接，可以记作 AB（A 与 B 连接），其中 A 和 B 都是有效括号字符串
嵌套，可以记作 (A)，其中 A 是有效括号字符串
嵌套深度：
类似地，我们可以定义任意有效括号字符串 s 的嵌套深度 depth(S)：
s 为空时，depth(“”) = 0
s 为 A 与 B 连接时，depth(A + B) = max(depth(A), depth(B))，其中 A 和 B 都是有效括号字符串
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));}

扩展阅读

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