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

问题描述

给你一个括号字符串 s ，它只包含字符 '(' 和 ')' 。一个括号字符串被称为平衡的当它满足：

任何左括号 '(' 必须对应两个连续的右括号 '))' 。

左括号 '(' 必须在对应的连续两个右括号 '))' 之前。

比方说 "())"， "())(())))" 和 "(())())))" 都是平衡的， ")()"， "()))" 和 "(()))" 都是不平衡的。

你可以在任意位置插入字符 '(' 和 ')' 使字符串平衡。

请你返回让 s 平衡的最少插入次数。

 

示例 1：

输入：s = "(()))"

输出：1

解释：第二个左括号有与之匹配的两个右括号，但是第一个左括号只有一个右括号。我们需要在字符串结尾额外增加一个 ')' 使字符串变成平衡字符串 "(())))" 。

示例 2：

输入：s = "())"

输出：0

解释：字符串已经平衡了。

示例 3：

输入：s = "))())("

输出：3

解释：添加 '(' 去匹配最开头的 '))' ，然后添加 '))' 去匹配最后一个 '(' 。

示例 4：

输入：s = "(((((("

输出：12

解释：添加 12 个 ')' 得到平衡字符串。

示例 5：

输入：s = ")))))))"

输出：5

解释：在字符串开头添加 4 个 '(' 并在结尾添加 1 个 ')' ，字符串变成平衡字符串 "(((())))))))" 。

代码

class Solution {

public:

    int minInsertions(string s) {

        //ans用于记录需要左括号和右括号的个数

        //need记录需要的右括号的个数

        int ans = 0,need = 0;

        for(char& c:s)

        {

            if(c == '(')

            {

                //一个左括号对应两个右括号

                need += 2;

                if(need % 2 == 1)

                {

                    ++ans;//加上一个右括号

                    --need;//右括号的需求减一

                }

            }

            else{

                --need;

                if(need == -1)

                {

                    //右括号多了一个，需要一个左括号

                    ++ans;

                    need = 1;//因为遇到一个右括号，所以只缺少一个右括号

                }

            }

        }

        return need + ans;

    }

};

结果

执行用时：120 ms, 在所有 C++ 提交中击败了23.28%的用户

内存消耗：11.9 MB, 在所有 C++ 提交中击败了99.72%的用户

巴特西

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

问题描述

代码

结果

最新文章

热门文章