宫水三叶的刷题日记

V1

2022/10/04阅读:23主题:前端之巅同款

921. 使括号有效的最少添加 : 简单成对括号问题

题目描述

这是 LeetCode 上的 921. 使括号有效的最少添加 ,难度为 中等

Tag : 「模拟」

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

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

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

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

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

示例 1:

输入:s = "())"

输出:1

示例 2:

输入:s = "((("

输出:3

提示:

  • s 只包含 '(' 和 ')' 字符

模拟

一个介绍过很多次的做法 : 将「有效括号问题」转化为「分值有效性」的数学判定。

使用 score 代指处理过程中的得分,将 ( 记为 +1,将 ) 记为 -1

一个有效的括号应当在整个过程中不出现负数,因此一旦 score 出现负数,我们需要马上增加 ( 来确保合法性;当整个 s 处理完后,还需要添加 socre 等同的 ) 来确保合法性。

Java 代码:

class Solution {
    public int minAddToMakeValid(String s) {
        int score = 0, ans = 0;
        for (char c : s.toCharArray()) {
            score += c == '(' ? 1 : -1;
            if (score < 0) {
                score = 0; ans++;
            }
        }
        return ans + score;
    }
}

TypeScript 代码:

function minAddToMakeValid(s: string): number {
    let scroe = 0, ans = 0
    for (const c of s) {
        scroe += c == '(' ? 1 : -1
        if (scroe < 0) {
            scroe = 0; ans++
        }
    }
    return ans + scroe
};

Python 代码:

class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        score, ans = 00
        for c in s:
            score += 1 if c == '(' else -1
            if score < 0:
                score = 0
                ans += 1
        return ans + score
  • 时间复杂度:
  • 空间复杂度:使用 charAt 代替 toCharArray 操作,复杂度为

最后

这是我们「刷穿 LeetCode」系列文章的第 No.921 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉

分类:

后端

标签:

后端

作者介绍

宫水三叶的刷题日记
V1