本文涉及知识点
C++栈
LeetCode1541. 平衡括号字符串的最少插入次数
给你一个括号字符串 s ，它只包含字符 ‘(’ 和 ‘)’ 。一个括号字符串被称为平衡的当它满足：
任何左括号 ‘(’ 必须对应两个连续的右括号 ‘))’ 。
左括号 ‘(’ 必须在对应的连续两个右括号 ‘))’ 之前。
比方说 “())”， “())(())))” 和 “(())())))” 都是平衡的， “)()”， “()))” 和 “(()))” 都是不平衡的。
你可以在任意位置插入字符 ‘(’ 和 ‘)’ 使字符串平衡。
请你返回让 s 平衡的最少插入次数。
示例 1：
输入：s = “(()))”
输出：1
解释：第二个左括号有与之匹配的两个右括号，但是第一个左括号只有一个右括号。我们需要在字符串结尾额外增加一个 ‘)’ 使字符串变成平衡字符串 “(())))” 。
示例 2：
输入：s = “())”
输出：0
解释：字符串已经平衡了。
示例 3：
输入：s = “))())(”
输出：3
解释：添加 ‘(’ 去匹配最开头的 ‘))’ ，然后添加 ‘))’ 去匹配最后一个 ‘(’ 。
示例 4：
输入：s = “((((((”
输出：12
解释：添加 12 个 ‘)’ 得到平衡字符串。
示例 5：
输入：s = “)))))))”
输出：5
解释：在字符串开头添加 4 个 ‘(’ 并在结尾添加 1 个 ‘)’ ，字符串变成平衡字符串 “(((())))))))” 。
提示：
1 <= s.length <= 105
s 只包含 ‘(’ 和 ‘)’ 。
栈
s[i]是（，则权值为1；)是-1。
p[i]是s[0…i]的权值和。
合法括号的条件：
条件一： ∀ \forall ∀i,p[i]>=0。
条件二：p.back()为0。
i从小到大处理p[i]，如果p[i]<0，则插入(，p[i]就变成0。
如果p.back() > 0，则增加p.back()个)。
时间复杂度：O(n)
预备处理
如果是偶数个连续)，删除一半，如果是奇数插入一个)后，再删除一半。这样预处理后，就由一个(对应两个))，变成1个(对应一个）。
代码
核心代码
class Solution {public:int minInsertions(string s) {int ret = 0;string t;for (int i = 0; i < s.length(); i++) {if ('(' == s[i]) {t += '(';continue;}t += s[i];if ((i + 1 < s.length()) && (')' == s[i + 1])) {i++;}else {ret++;}}int cur = 0;for (const auto& ch : t) {cur += ('(' == ch ? 1 : -1);if (cur < 0) {cur = 0;ret++;}}return ret + cur * 2;}};
代码
string s;TEST_METHOD(TestMethod11){s = "(()))";auto res = Solution().minInsertions(s);AssertEx(1, res);}TEST_METHOD(TestMethod12){s = "())";auto res = Solution().minInsertions(s);AssertEx(0, res);}TEST_METHOD(TestMethod13){s = "))())(";auto res = Solution().minInsertions(s);AssertEx(3, res);}TEST_METHOD(TestMethod14){s = "((((((";auto res = Solution().minInsertions(s);AssertEx(12, res);}TEST_METHOD(TestMethod15){s = ")))))))";auto res = Solution().minInsertions(s);AssertEx(5, res);}
扩展阅读
| 我想对大家说的话 |
|---|
| 工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。 |
| 学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作 |
| 有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注 |
| 闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
| 失败+反思=成功 成功+反思=成功 |
视频课程
先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
