侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【贪心, 模拟栈】使括号有效的最少添加

GabrielxD
2022-10-04 / 0 评论 / 0 点赞 / 18 阅读 / 587 字 / 正在检测是否收录...

题目

921. 使括号有效的最少添加


只有满足下面几点之一,括号字符串才是有效的:

  • 它是一个空字符串,或者
  • 它可以被写成 AB (A 与 B 连接), 其中 A 和 B 都是有效字符串,或者
  • 它可以被写作 (A),其中 A 是有效字符串。

给定一个括号字符串 s ,移动N次,你就可以在字符串的任何位置插入一个括号。

  • 例如,如果 s = "()))" ,你可以插入一个开始括号为 "(()))" 或结束括号为 "())))"

返回 为使结果字符串 s 有效而必须添加的最少括号数

示例 1:

输入:s = "())"
输出:1

示例 2:

输入:s = "((("
输出:3

提示:

  • 1 <= s.length <= 1000
  • s 只包含 '(' 和 ')' 字符。

解题

方法一:贪心 模拟栈

思路

既然要使 s 有效且还要添加最少的括号,那么我们可以在且仅在括号序列无效的时候添加括号。

具体来说:维护一个栈,遍历字符串中每个字符,如果当前字符是左括号就入栈,如果是右括号就出栈,但如果当前字符是右括号需要出栈的时候栈已经为空了,就说明左边已经没有可以和它匹配的左括号了,这时需要添加一个左括号(++require)。
那么如果右括号没了怎么办?如果右括号没了不会出现栈空的情况,但是在字符串遍历完成后没匹配右括号的左括号都会留在栈中,也就是说,此时栈的大小就是最少需要添加的右括号的数量。
这样下来,require + stk.size() 就是我们要求的答案。

我们注意到,字符串中只会存在一种括号( ())所以我们不必真的去维护一个栈,而是使用一个计数(cnt)来表示栈目前的大小就可以了。

代码

class Solution {
    public int minAddToMakeValid(String s) {
        int require = 0, cnt = 0;
        for (char ch : s.toCharArray()) {
            if (ch == '(') ++cnt;
            else if (cnt > 0) --cnt;
            else ++require;
        }
        return require + cnt;
    }
}
0

评论区