【每日算法Day 87】今天我脱单了，所以大家不用做题了！

题目链接

LeetCode 1111. 有效括号的嵌套深度^[1]

题目描述

题面太长晦涩不想看，请直接跳到最后一段。

有效括号字符串 仅由 "(" 和 ")" 构成，并符合下述几个条件之一：

• 空字符串
• 连接，可以记作 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]解释：拆成 "()" 和 "()()" ，最大嵌套深度为 1

示例2

输入：seq = "()(())()"输出:[0,0,0,1,1,0,1,1]解释：拆成 "()()" 和 "()()" ，最大嵌套深度为 1

说明：

• 1 <= text.size <= 10000

题解

既然想要两个子序列的嵌套深度中较大者尽量小，那么我们最好能够让两个子序列的嵌套

伪代码也就是：

if c = '('    cnt := cnt + 1    mask := cnt&1else    mask := cnt&1    cnt := cnt - 1

简化

其实我们可以注意到，不管是加一还是减一，奇偶性的变化都是一致的，也就是减一之后的奇偶性和加一之后是相同的。

所以我们把减一也变成加一，那么不管遇到什么括号，都是 加一了，那不就变成了下标  了吗？

我们把上面的伪代码按照这种思路改变一下：

if c = '('    cnt := cnt + 1    mask := cnt&1else    mask := cnt&1    cnt := cnt + 1

if c = '('    mask := (i+1)&1else    mask := i&1

继续改写一下，让形式统一一点：

if c = '('    mask := ~(i&1)else    mask := i&1

那么最后就可以把这两种情况合并了，也就是标记值直接就等于 (i&1)^(c='(') 。

当然我是从代码的角度，从奇偶性推过来的，官方题解是直接严格证明了正确性：

官方题解：LeetCode 1111. 有效括号的嵌套深度^[2]

代码

c++

classSolution {
public:   
vector<int>maxDepthAfterSplit(stringseq) {   
intcnt=0;     
vector<int>res;    
for (autoc : seq) {      
if (c=='(') {      
res.push_back((++cnt)&1);    
            } else {       
res.push_back((cnt--)&1);    
            }      
        }       
returnres; 
    }
};

简化（c++）

classSolution {
public:   
vector<int>maxDepthAfterSplit(stringseq) {   
vector<int>res;    
for (inti=0, sz=seq.size(); i<sz; ++i) {  
res.push_back((i&1)^(seq[i]=='('));   
        }      
returnres; 
    }
};

简化（python）

classSolution: 
defmaxDepthAfterSplit(self, seq: str) ->List[int]:   
res= []      
fori, cinenumerate(seq):   
res.append((i&1)^(c=='(')) 
returnres

参考资料

[1]

LeetCode 1111. 有效括号的嵌套深度: https://leetcode-cn.com/problems/maximum-nesting-depth-of-two-valid-parentheses-strings/

[2]

官方题解：LeetCode 1111. 有效括号的嵌套深度: https://leetcode-cn.com/problems/maximum-nesting-depth-of-two-valid-parentheses-strings/solution/you-xiao-gua-hao-de-qian-tao-shen-du-by-leetcode-s/

作者简介：godweiyang，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~