队列、栈专题

不要纠结，干就完事了，熟练度很重要！！！多练习，多总结！！！

LeetCode 20. 有效的括号

解题思路

遇到左括号就入栈，遇到右括号就去栈中寻找最近的左括号，看是否匹配，最后记得检查栈是否清空了，这才算匹配完成。

代码实现

class Solution {public boolean isValid(String s) {Stack<Character> stack = new Stack<>();for(char c:s.toCharArray()){if(c == '(' || c == '{' || c == '['){stack.push(c);}else if(!stack.isEmpty() && leftOf(c) == stack.peek()){stack.pop();}else {return false;}}return stack.isEmpty();}public char leftOf(char c){if(c == ')'){return '(';}else if(c == ']'){return '[';}else if(c == '}'){return '{';}return ' ';}
}

LeetCode 921. 使括号有效的最少添加

解题思路

核心思路是以左括号为基准，通过维护对右括号的需求数need，来计算最小的插入次数。需要注意两个地方：

1. 当need == -1的时候意味着什么？

因为只有遇到右括号)的时候才会need–，need == -1意味着右括号太多了，所以需要插入左括号。
比如说s = “))“这种情况，需要插入 2 个左括号，使得s变成”()()”，才是一个合法括号串。

2. 算法为什么返回res + need？

因为res记录的左括号的插入次数，need记录了右括号的需求，当 for 循环结束后，若need不为 0，那么就意味着右括号还不够，需要插入。
比如说s = “))(“这种情况，插入 2 个左括号之后，还要再插入 1 个右括号，使得s变成”()()()”，才是一个合法括号串。

代码实现

class Solution {public int minAddToMakeValid(String s) {int res = 0, need = 0;for(char c: s.toCharArray()){if(c == '('){need++;}else if(c == ')'){need--;if(need == -1){res++;need = 0;}}}return res+need;}
}

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

解题思路

1. 当need == -1时，意味着我们遇到一个多余的右括号，显然需要插入一个左括号。

if (s[i] == ')') {need--;// 说明右括号太多了if (need == -1) {// 需要插入一个左括号res++;// 同时，对右括号的需求变为 1need = 1;}
}

2. 当遇到左括号时，若对右括号的需求量为奇数，需要插入 1 个右括号。因为一个左括号需要两个右括号嘛，右括号的需求必须是偶数。（记住res和need代表含义不同，一加一减不可抵消，在need==-1时还有额外判断逻辑）

if (s[i] == '(') {need += 2;if (need % 2 == 1) {// 插入一个右括号res++;// 对右括号的需求减一need--;}
}

代码实现

class Solution {public int minInsertions(String s) {int res = 0, need = 0;for(char c :s.toCharArray()){if(c == '('){need+=2;if (need % 2 == 1) {res++;need--;}}else if(c == ')'){need--;if(need == -1){res++;need = 1;}}}return res+need;}
}

总结

本题来源于Leetcode中 归属于队列、栈类型题目。
同许多在算法道路上不断前行的人一样，不断练习，修炼自己！
如有博客中存在的疑问或者建议，可以在下方留言一起交流，感谢各位！

觉得本博客有用的客官，可以给个点赞+收藏哦！ 嘿嘿

喜欢本系列博客的可以关注下，以后除了会继续更新面试手撕代码文章外，还会出其他系列的文章！