平衡括号字符串的最少插入次数
难度:
标签:
题目描述
代码结果
运行时间: 64 ms, 内存: 17.0 MB
/*
题目思路:
使用Java Stream实现与常规Java方法相同的逻辑。
通过IntStream遍历字符串,并使用AtomicInteger来保持计数器状态。
*/
import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.IntStream;
public int minInsertions(String s) {
AtomicInteger balance = new AtomicInteger(0);
AtomicInteger insertions = new AtomicInteger(0);
IntStream.range(0, s.length()).forEach(i -> {
char c = s.charAt(i);
if (c == '(') {
balance.addAndGet(2);
if (balance.get() % 2 != 0) {
insertions.incrementAndGet();
balance.decrementAndGet();
}
} else {
balance.decrementAndGet();
if (balance.get() < 0) {
insertions.incrementAndGet();
balance.addAndGet(2);
}
}
});
return insertions.get() + balance.get();
}
解释
方法:
题解首先通过将字符串中的连续两个 ')' 替换为一个 '*' 简化表示,这样每个 '*' 代表一个有效的 '))'。然后,计算剩余的单独 ')' 的数量,因为这些 ')' 是无法匹配的,需要额外的 '(' 来匹配。接着,将这些无法匹配的 ')' 也替换为 '*'。然后,通过循环消除形如 '(*' 的模式,这种模式表示一个 '(' 直接匹配了后面的 '))'。最后,统计剩余的 '*' 和 '(' 的数量,每个 '*' 需要一个 ')' 来匹配,每个 '(' 需要两个 ')' 来匹配。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么在算法中首先将字符串中的连续两个 ')' 替换为一个 '*' 来简化问题?这种替换对解决问题有什么具体帮助?
▷🦆
在替换操作后,算法是如何处理剩余的单独 ')' 的?请解释为什么需要将这些 ')' 转换为 '*' 来进一步处理。
▷🦆
循环消除 '(*' 模式的具体逻辑是什么?这种模式在字符串中代表了什么意义,为什么选择消除它?
▷🦆
题解中提到,最后需要统计剩余的 '*' 和 '(' 的数量来计算最少插入次数。能否详细说明这一计算过程,特别是为何每个 '(' 需要两个 ')' 来匹配?
▷