資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用 Python 查詢平衡括號字串所需的最少插入次數的程式
假設我們有一個字串 s，其中包含開括號和閉括號 '(' 和 ')'。當滿足以下條件時，我們可以說一個括號字串是平衡的：
任何左括號 '(' 都對應兩個連續的右括號 '))'。
左括號 '(' 必須在對應的兩個連續右括號 '))' 之前。
例如，"())"、"())(())))" 是平衡的，但 ")()"、"()))" 不是。如果我們有這樣的字串，我們必須計算括號（開或閉）的數量以使字串平衡。
因此，如果輸入類似於 s = "(())))))"，則輸出將為 1，因為如果我們將其拆分，我們可以得到 "( ()) )) ))"，所以我們需要一個左括號來使字串 "( ()) ()) ))" 平衡。
為了解決這個問題，我們將遵循以下步驟：
o := 0，n := s 的大小
ret := 0，i := 0
當 i < n 時，執行以下操作：
如果 s[i] 與 '(' 相同，則
o := o + 1
否則，
如果 i + 1 < n 且 s[i + 1] 與 ')' 相同，則
如果 o 為 0，則
ret := ret + 1
否則，
o := o - 1
i := i + 1
否則，
ret := ret + 1
如果 o 為 0，則
ret := ret + 1
否則，
o := o - 1
i := i + 1
返回 ret + 2 * o
讓我們看看以下實現，以更好地理解：
示例
def solve(s):
o = 0
n = len(s)
ret = 0
i = 0
while i < n:
if s[i] == '(':
o += 1
else:
if i + 1 < n and s[i + 1] == ')':
if not o:
ret += 1
else:
o -= 1
i += 1
else:
ret += 1
if not o:
ret += 1
else:
o -= 1
i += 1
return ret + 2 * o
s = "(())))))"
print(solve(s))輸入
"(())))))"
輸出
3
更新於: 2021年5月29日
727 次瀏覽
廣告