leetcode
leetcode 1401 ~ 1450
平衡括号字符串的最少插入次数

平衡括号字符串的最少插入次数

难度:

标签:

题目描述

代码结果

运行时间: 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)

代码细节讲解

🦆
为什么在算法中首先将字符串中的连续两个 ')' 替换为一个 '*' 来简化问题?这种替换对解决问题有什么具体帮助?
在算法中,将连续的两个 ')' 替换为一个 '*' 是为了简化对有效配对的处理。在问题中,每个 '(' 可以关闭两个 ')',因此通过将每对 ')' 视为一个单元('*'),可以更直观和简单地处理和计算需要的插入次数。这种替换有助于将问题转化为更简单的形式,即只需关注单一类型的配对 ('*' 与 '(') 而不是多种类型的 ')',从而减少错误并提高算法的可读性和实现的简洁性。
🦆
在替换操作后,算法是如何处理剩余的单独 ')' 的?请解释为什么需要将这些 ')' 转换为 '*' 来进一步处理。
在替换连续的两个 ')' 为 '*' 后,可能会剩下一些单独的 ')'。这些单独的 ')' 无法形成有效的配对,因此需要额外的 '(' 来与之匹配。算法将这些单独的 ')' 也转换为 '*',使得后续处理统一且简单,即处理所有的 '*' 都需要配对的 '('。这样做减少了处理不同情况的复杂性,允许算法统一处理所有需要 ')' 的情况。
🦆
循环消除 '(*' 模式的具体逻辑是什么?这种模式在字符串中代表了什么意义,为什么选择消除它?
'(*' 模式代表一个 '(' 后紧接着一个 '*'(即 '))'),表示这个 '(' 已经匹配了紧随其后的两个 ')'。在算法中,循环消除这种模式的目的是减少未匹配的 '(' 和 '*',从而准确计算出需要额外插入的字符数。每次消除一个 '(*' 模式,意味着一个 '(' 已经成功匹配了两个 ')',因此这两个字符不再需要额外的配对,可以从字符串中移除,简化后续的计算。
🦆
题解中提到,最后需要统计剩余的 '*' 和 '(' 的数量来计算最少插入次数。能否详细说明这一计算过程,特别是为何每个 '(' 需要两个 ')' 来匹配?
在进行了上述替换和消除操作后,字符串中可能还剩下一些未匹配的 '(' 和 '*'. 由于每个 '*' 代表一个已经成对的 ')',因此每个 '*' 需要一个 ')' 来完成配对。而每个 '(' 需要两个 ')' 来匹配,因为在原始问题定义中,一个 '(' 旨在匹配两个 ')'. 因此,计算最少插入次数时,对于每个剩余的 '*',增加一个 ')' 的需求;对于每个 '(',增加两个 ')' 的需求。这样计算出的总数即为需要插入的 ')' 数量,以确保所有的括号都能正确配对。

相关问题