本文涉及知识点
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));
}
