AcWing 每日一题2020/09/15

题目描述

给定一个括号字符串s，它只包含字符（和）。一个括号字符串被称为平衡的当它满足：

任何左括号（必须对应两个连续的右括号）），左括号（’必须在对应的连续两个右括号））’之前。

比方说“（））“，“（））（（））））“和“（（））（））））“都是平衡的，“）（）”，”（）））”和“（（）））”都是不平衡的。

你可以在任意位置插入字符（和）使字符串平衡。
请你返回让s平衡的最少插入次数。

样例：

输入：s=”（（）））”
输出：1
解释：第二个左括号有与之匹配的两个右括号，但是第一个左括号只有一个右括号。我们需要在字符串结尾额外增加一个）’使字符串变成平衡字符串”（（））））”。

输入: s = “) ())(“
输出: 3
解释:添加’(‘去匹配最开头的’))’,然后添加‘))’去匹配最后一个(

限制
1 <= s. length <= 10^5

算法思路

算法(分类讨论) O(n)

1.维护一个统计值v,初始值为0, (价值为2, )价值为1.然后遍历字符串。

2.如果遇到(
如果v>0且v是奇数,则说明之前需要补一个) ,然后v减1.\
如果v<0,则说明缺(,至少缺-v/2个(.
在这个情况下,如果v仍然是奇数,则说明有一个落单的),需要一个额外的（和）
v置0

3.如果遇到) ,则v自减1.

4.遍历结束后,如果v>0,则说明需要补v个);否则,按照之前v<0补全括号。

时间复杂度·遍历字符串一次,故总时间复杂度为0(n).

空间复杂度仅需要常数的额外空间。

C++代码实现

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    string s;
    cin >> s;
    int v = 0;
    int res = 0;
    for (int i=0; i< s.size(); i++)
    {
        if (s[i] == '(')
        {
            if (v > 0 && v % 2==1) res++, v--;
            else if (v < 0)
            {
                res += (-v/2);
                if (v%2==-1) res += 2;
                v = 0;
            }
            v += 2;  // 遇到'('加2
        }
        else
        {
            v--;  // 遇到')'减1
        }
    }

    if (v > 0) res+=v;
    else if (v < 0)
    {
        res += (-v/2);
        if (v%2==-1) res += 2;
        v = 0;
    }

    cout << res << endl;
    return 0;
}