数据结构
网络
关系数据库管理系统
操作系统
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 次浏览
广告