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