class Solution {
public:
int minInsertions(string s) {
}
};
1541. 平衡括号字符串的最少插入次数
给你一个括号字符串 s ，它只包含字符 '(' 和 ')' 。一个括号字符串被称为平衡的当它满足：
'(' 必须对应两个连续的右括号 '))' 。'(' 必须在对应的连续两个右括号 '))' 之前。比方说 "())"， "())(())))" 和 "(())())))" 都是平衡的， ")()"， "()))" 和 "(()))" 都是不平衡的。
你可以在任意位置插入字符 '(' 和 ')' 使字符串平衡。
请你返回让 s 平衡的最少插入次数。
示例 1：
输入：s = "(()))" 输出：1 解释：第二个左括号有与之匹配的两个右括号，但是第一个左括号只有一个右括号。我们需要在字符串结尾额外增加一个 ')' 使字符串变成平衡字符串 "(())))" 。
示例 2：
输入：s = "())" 输出：0 解释：字符串已经平衡了。
示例 3：
输入：s = "))())("
输出：3
解释：添加 '(' 去匹配最开头的 '))' ，然后添加 '))' 去匹配最后一个 '(' 。
示例 4：
输入：s = "(((((("
输出：12
解释：添加 12 个 ')' 得到平衡字符串。
示例 5：
输入：s = ")))))))"
输出：5
解释：在字符串开头添加 4 个 '(' 并在结尾添加 1 个 ')' ，字符串变成平衡字符串 "(((())))))))" 。
提示：
1 <= s.length <= 10^5s 只包含 '(' 和 ')' 。原站题解
golang 解法, 执行用时: 24 ms, 内存消耗: 6.2 MB, 提交时间: 2023-09-21 23:40:28
func minInsertions(s string) int {
ans := 0 // 记录插入次数
need := 0 // 记录右括号的需求量
for _, c := range s {
if string(c)=="(" {
need += 2 // 对右括号的需求+2
if need%2 == 1 { //左括号对右括号的需求必须为偶数
ans++
need--
}
}
if string(c)==")" {
need-- // 对右括号的需求-1
if need==-1 {
ans++ // 需插入一个左括号
need = 1 // 同时对右括号的需求变为1
}
}
}
return ans + need
}
python3 解法, 执行用时: 136 ms, 内存消耗: 16.4 MB, 提交时间: 2023-09-21 23:40:15
class Solution:
def minInsertions(self, s: str) -> int:
length = len(s)
insertions = leftCount = index = 0
while index < length:
if s[index] == "(":
leftCount += 1
index += 1
else:
if leftCount > 0:
leftCount -= 1
else:
insertions += 1
if index < length - 1 and s[index + 1] == ")":
index += 2
else:
insertions += 1
index += 1
insertions += leftCount * 2
return insertions
cpp 解法, 执行用时: 28 ms, 内存消耗: 12.3 MB, 提交时间: 2023-09-21 23:39:51
class Solution {
public:
int minInsertions(string s) {
int insertions = 0;
int leftCount = 0;
int length = s.size();
int index = 0;
while (index < length) {
char c = s[index];
if (c == '(') {
leftCount++;
index++;
} else {
if (leftCount > 0) {
leftCount--;
} else {
insertions++;
}
if (index < length - 1 && s[index + 1] == ')') {
index += 2;
} else {
insertions++;
index++;
}
}
}
insertions += leftCount * 2;
return insertions;
}
};
java 解法, 执行用时: 10 ms, 内存消耗: 42.8 MB, 提交时间: 2023-09-21 23:39:40
class Solution {
public int minInsertions(String s) {
int insertions = 0;
int leftCount = 0;
int length = s.length();
int index = 0;
while (index < length) {
char c = s.charAt(index);
if (c == '(') {
leftCount++;
index++;
} else {
if (leftCount > 0) {
leftCount--;
} else {
insertions++;
}
if (index < length - 1 && s.charAt(index + 1) == ')') {
index += 2;
} else {
insertions++;
index++;
}
}
}
insertions += leftCount * 2;
return insertions;
}
}