1111、有效括号的嵌套深度
有效括号字符串 仅由 “(“ 和 “)” 构成，并符合下述几个条件之一：
- 空字符串
- 连接，可以记作 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，而")("和"(()"都不是有效括号字符串。
给你一个有效括号字符串 seq，将其分成两个不相交的子序列 A 和 B，且 A 和 B 满足有效括号字符串的定义（注意：A.length + B.length = seq.length）。
现在，你需要从中选出 任意 一组有效括号字符串 A 和 B，使 max(depth(A), depth(B)) 的可能取值最小。
返回长度为 seq.length 答案数组 answer ，选择 A 还是 B 的编码规则是：如果 seq[i] 是 A 的一部分，那么 answer[i] = 0。否则，answer[i] = 1。即便有多个满足要求的答案存在，你也只需返回 一个。
示例 1：
输入：seq = "(()())"
输出：[0,1,1,1,1,0]
示例 2：
输入：seq = "()(())()"
输出：[0,0,0,1,1,0,1,1]
提示：
1 <= text.size <= 10000
链接：https://leetcode-cn.com/problems/maximum-nesting-depth-of-two-valid-parentheses-strings
题解
将原串进行拆解，拆成不相交的 A 和 B，同时满足：
length(seq) = length(A) + length(B)max(length(A),length(B)) 尽可能小
只有将seq进行对半拆解，才行。要实现这样的对半分配，我们只需要把奇数层的 ( 分配给 A，偶数层的 ( 分配给 B 即可
“不相交” 其实只要 A 和 B 是seq的两部分就行。
1、用栈进行括号匹配
class Solution {
public int[] maxDepthAfterSplit(String seq) {
int depth = 0;
int[] ans = new int[seq.length()];
int index = 0;
for (char ch : seq.toCharArray()) {
if (ch == '(') {
++depth;
ans[index++] = depth % 2;
} else {
ans[index++] = depth % 2;
--depth;
}
}
return ans;
}
// 求括号字符串的嵌套深度
public int[] depthOfParenthesisStrig(String seq) {
int depth = 0;
if (seq.equals("")) {return depth;}
int ans = 0
for (char ch : seq.toCharArray()) {
if (ch == '(') {
++depth;
ans = depth;
} else {
--depth;
}
}
return ans;
}
}
分析规律
我们还是使用上面的例子 (()(())())，但这里我们把 ( 和 ) 的嵌套深度分成两行：
括号序列 ( ( ) ( ( ) ) ( ) )
下标编号 0 1 2 3 4 5 6 7 8 9
嵌套深度 1 2 - 2 3 - - 2 - -
嵌套深度 - - 2 - - 3 2 - 2 1
有没有发现什么规律？
左括号 ( 的下标编号与嵌套深度的奇偶性相反，也就是说：
下标编号为奇数的 (，其嵌套深度为偶数，分配给 B；
下标编号为偶数的 (，其嵌套深度为奇数，分配给 A。
右括号 ) 的下标编号与嵌套深度的奇偶性相同，也就是说：
下标编号为奇数的 )，其嵌套深度为奇数，分配给 A；
下标编号为偶数的 )，其嵌套深度为偶数，分配给 B。
这样以来，我们只需要根据每个位置是哪一种括号以及该位置的下标编号，就能确定将对应的对应的括号分到哪个组了。
class Solution {
public int[] maxDepthAfterSplit(String seq) {
if (seq.equals("")) {
return new int[]{};
}
int[] ans = new int[seq.length()];
char[] chs = seq.toCharArray();
for (int i = 0;i < chs.length;i++) {
// 灵活运用位运算
ans[i] = i & 1 ^ ((chs[i] == '(')? 1 : 0);
}
return ans;
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
