图解LeetCode——921. 使括号有效的最少添加（难度：中等） 一、题目 只有满足下面几点之一，括号字符串才是有效的：它是一个空字符串，或者它可以被写成 （ 与 连接）, 其中 和 都是有效字符串，或者它可以被写作 ，其中 是有效字符串。 给定一个括号字符串 ，移动N次，你就可以在字符串的任何位置插入一个括号。 例如，如果 ，你可以插入一个开始括号为 或结束括号为 。 返回 为使结果字符串 有效而必须添加的最少括号数。 二、示例 2.1> 示例 1： 【输入】s = “())”【输出】1 2.2> 示例 2： 【输入】s = “(((“【输出】3 提示： <= s.length <= 只包含 和 字符。 三、解题思路 这道题的题目描述真的挺让人费解的。其实题目的意思就是，我们如果想要配对好所有的括号，需要在原有字符串的基础上，添加多少个括号（可能是左括号、也可能是右括号）。那么针对于这种配对类型类型的题目，第一个想法就是使用堆栈来实现。当然，对于的特殊性，即：左括号 + 右括号 。我们也可以根据这个规律去计算。如下是两种解题算法的详细解释。 3.1> 思路1：利用栈特性去计算 我们可以通过对字符串进行每个字符的遍历，放到堆栈中。当发现栈顶字符是，待入栈的字符是，则符合括号匹配的情况。那么，此时我们只需将栈顶字符出栈即可。而针对于其他情况，我们都是将遍历的字符入栈即可。那么字符串s遍历完毕之后，我们来调用方法计算存储的字符长度，返回的长度就是这道题的结果。具体逻辑如下图所示：
针对该思路的代码实现，请参见：代码实现 4.1> 利用栈特性去计算 3.2> 思路2：找规律去匹配 通过题目的【提示】 只包含 和 字符。所以， 对于两个字符的匹配一共有如下图的四种情况。那么，只有【情况一】是会匹配成功的，而其他的情况都匹配失败。那么我们创建两个变量：（左括号数量）和（右括号数量）。如果遍历到字符是左括号，则执行如果遍历到字符是右括号，并且leftCount不为0，则执行如果遍历到字符是右括号，并且leftCount等于0，则执行
针对该思路的代码实现，请参见：代码实现 4.2> 找规律去匹配 四、代码实现 4.1> 实现1：利用栈特性去计算 
4.2> 实现2：找规律去匹配 
今天的文章内容就这些了：写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。 更多技术干货，欢迎大家“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」 往期推荐
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/39968.html
