数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究Python 中两个有效括号字符串的最大嵌套深度
假设我们有一个字符串，该字符串是一个有效的括号字符串（表示为 VPS），当且仅当它仅由“（”和“）”字符组成，并且满足以下属性：
它是空字符串，或者
它可以写成 AB，其中 A 和 B 都是 VPS，或者
它可以写成 (A)，其中 A 是 VPS。
我们还可以定义任何 VPS S 的嵌套深度 depth(S)，如下所示：
depth("") = 0
depth(A + B) = max(depth(A), depth(B))，其中 A 和 B 是 VPS
depth("(" + A + ")") = 1 + depth(A)，其中 A 是 VPS。
如果我们有一个 VPS seq，我们必须将其拆分为两个不相交的子序列 A 和 B，使得 A 和 B 都是 VPS（并且 A 的长度 + B 的长度 = seq 的长度）。现在，如果我们选择任何这样的 A 和 B 使得 max(depth(A), depth(B)) 是最小可能的值。然后我们必须找到一个答案数组（长度为 seq），它对 A 和 B 的这种选择进行编码：如果 seq[i] 是 A 的一部分，则 answer[i] = 0，否则 answer[i] = 1。
因此，如果输入类似于“()(())()”，则输出将为 [1,1,1,0,1,0,1,1]
为了解决这个问题，我们将遵循以下步骤：
n := seq 的长度，res := 一个长度为 n 的 0 数组
c1, c2 := 0, 0
for i in range 0 to n – 1
if seq[i] = ‘(’
if c1 < c2，则将 c1 增加 1，否则将 c2 增加 1 并将 res[i] := 1
否则
if c1 > c2，则将 c1 减小 1，否则将 c2 减小 1 并将 res[i]:= 1
return res
让我们看看下面的实现以获得更好的理解：
示例
class Solution(object):
def maxDepthAfterSplit(self, seq):
n = len(seq)
res = [0] *n
c1,c2= 0,0
for i in range(n):
if seq[i] == '(':
if c1<c2:
c1+=1
else:
c2+=1
res[i]=1
else:
if c1>c2:
c1-=1
else:
c2-=1
res[i]=1
return res
ob = Solution()
print(ob.maxDepthAfterSplit("()(())()"))输入
"()(())()"
输出
[1, 1, 1, 0, 1, 0, 1, 1]
223 次查看
