本文主要是介绍稀碎从零算法笔记Day17-LeetCode:有效的括号,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题型:栈
链接:20. 有效的括号 - 力扣(LeetCode)
来源:LeetCode
题目描述(红字为笔者添加)
给定一个只包括 '('
,')'
,'{'
,'}'
,'['
,']'
的字符串 s
,判断字符串是否有效。
有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
正确情况: ( { [ ] } ) 错误情况:( { )}
题目样例
示例 1:
输入:s = "()" 输出:true
示例 2:
输入:s = "()[]{}" 输出:true
示例 3:
输入:s = "(]" 输出:false
提示:
1 <= s.length <= 104
s
仅由括号'()[]{}'
组成
题目思路
题目描述机翻,推荐看英语原文/笑
一开始没思路,看题解对于这种【对称型匹配】,适合用【栈】来匹配
具体思路就是:遍历字符串 ①如果遍历得到的 char 是【左括弧】——这里我们先不讨论是哪一种,那么就在栈中压入一个【对应的右括弧】。 ②如果遍历得到的char是【不是左括弧】,那么就从栈中弹出栈顶元素——前提是栈顶元素和 char 是同一种【右括弧】
C++代码
class Solution {
public:bool isValid(string s) {//利用栈匹配括弧(栈适合做“对称匹配类”)// 遍历字符串:碰到【左括弧】,往栈中压入【对应的右括弧】// 碰到【右括弧】,栈中弹出【对应的左括弧】int len=s.length();if(len%2 != 0)return 0;stack<char> stack_ch;for(int i=0;i<len;i++){if(s[i] == '(') {stack_ch.push(')');continue;}else if(s[i] == '{') {stack_ch.push('}');continue;}else if(s[i] == '[') {stack_ch.push(']');continue;}else if(stack_ch.empty() || s[i] != stack_ch.top())//表示栈中没有要匹配的括弧 return 0;elsestack_ch.pop();//相等,说明市对应的【右括弧】}return stack_ch.empty();//最后如果栈为空,说明【左括弧】和【右括弧】想对应。不为空 说明有多余的【左括弧】}
};
结算页面
这篇关于稀碎从零算法笔记Day17-LeetCode:有效的括号的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!