資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
