外贸精品网站建设,晚上睡不着网站2021免费,如何新做的网站让百度快速收录,上海鹭城建设集团网站队列、栈专题 LeetCode 20. 有效的括号解题思路代码实现 LeetCode 921. 使括号有效的最少添加解题思路代码实现 LeetCode 1541. 平衡括号字符串的最少插入次数解题思路代码实现 总结 不要纠结#xff0c;干就完事了#xff0c;熟练度很重要#xff01;#xff01;#xff… 队列、栈专题 LeetCode 20. 有效的括号解题思路代码实现 LeetCode 921. 使括号有效的最少添加解题思路代码实现 LeetCode 1541. 平衡括号字符串的最少插入次数解题思路代码实现 总结 不要纠结干就完事了熟练度很重要多练习多总结 LeetCode 20. 有效的括号 解题思路
遇到左括号就入栈遇到右括号就去栈中寻找最近的左括号看是否匹配最后记得检查栈是否清空了这才算匹配完成。
代码实现
class Solution {public boolean isValid(String s) {StackCharacter 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来计算最小的插入次数。需要注意两个地方
当need -1的时候意味着什么
因为只有遇到右括号)的时候才会need–need -1意味着右括号太多了所以需要插入左括号。 比如说s “))“这种情况需要插入 2 个左括号使得s变成”()()”才是一个合法括号串。
算法为什么返回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 resneed;}
}LeetCode 1541. 平衡括号字符串的最少插入次数 解题思路
当need -1时意味着我们遇到一个多余的右括号显然需要插入一个左括号。
if (s[i] )) {need--;// 说明右括号太多了if (need -1) {// 需要插入一个左括号res;// 同时对右括号的需求变为 1need 1;}
}当遇到左括号时若对右括号的需求量为奇数需要插入 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 (){need2;if (need % 2 1) {res;need--;}}else if(c )){need--;if(need -1){res;need 1;}}}return resneed;}
}总结
本题来源于Leetcode中 归属于队列、栈类型题目。 同许多在算法道路上不断前行的人一样不断练习修炼自己 如有博客中存在的疑问或者建议可以在下方留言一起交流感谢各位
觉得本博客有用的客官可以给个点赞收藏哦 嘿嘿
喜欢本系列博客的可以关注下以后除了会继续更新面试手撕代码文章外还会出其他系列的文章
