做网站都用什么软件,微信小程序怎么做活动,北京注册公司地址,购物网站开发背景原题链接#x1f517;#xff1a;有效的括号 难度#xff1a;简单⭐️
题目
给定一个只包括 ‘(’#xff0c;‘)’#xff0c;‘{’#xff0c;‘}’#xff0c;‘[’#xff0c;‘]’ 的字符串 s #xff0c;判断字符串是否有效。
有效字符串需满足#xff1a; …原题链接有效的括号 难度简单⭐️
题目
给定一个只包括 ‘(’‘)’‘{’‘}’‘[’‘]’ 的字符串 s 判断字符串是否有效。
有效字符串需满足
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。
示例 1
输入s “()” 输出true
示例 2
输入s “()[]{}” 输出true
示例 3
输入s “(]” 输出false
提示
1 s.length 104s 仅由括号 ‘()[]{}’ 组成
栈
数据结构中的栈Stack是一种遵循后进先出Last In First OutLIFO原则的线性数据结构。在栈中数据的添加和删除都发生在栈顶。栈的两个主要操作是
压栈Push将一个元素添加到栈顶。弹栈Pop移除栈顶的元素并返回它。
此外栈还可能支持以下操作
查看栈顶元素Peek/Top返回栈顶元素但不从栈中移除它。检查栈是否为空IsEmpty判断栈是否没有任何元素。获取栈的大小Size返回栈中元素的数量。
栈在计算机科学中有着广泛的应用例如
函数调用和返回的实现每次函数调用时其返回地址和局部变量会被压入调用栈。括号匹配问题使用栈来检查字符串中的括号是否正确闭合。撤销操作Undo在编辑器或绘图软件中用户的操作可以被压入栈中以便随时撤销。深度优先搜索DFS在图或树的遍历中使用栈来存储待访问的节点。
栈的实现可以基于数组或链表。数组实现的栈具有固定的大小而链表实现的栈则可以动态地增长和收缩。
栈的 C 实现示例
以下是使用 C 标准模板库STL中的 std::stack 容器实现栈的一个简单示例
#include iostream
#include stackint main() {std::stackint myStack;// 压栈操作myStack.push(10);myStack.push(20);myStack.push(30);// 查看栈顶元素std::cout Top element is: myStack.top() std::endl;// 弹栈操作myStack.pop();std::cout Top element after one pop is: myStack.top() std::endl;// 检查栈是否为空if (!myStack.empty()) {std::cout Stack is not empty. std::endl;}// 获取栈的大小std::cout Size of stack: myStack.size() std::endl;return 0;
}这个示例展示了如何创建一个整数类型的栈执行压栈和弹栈操作查看栈顶元素检查栈是否为空以及获取栈的大小。
题解
解题思路 LeetCode 上的 “有效的括号”Valid Parentheses问题是一个经典的栈Stack应用问题。这个问题要求判断一个字符串中的括号是否正确配对。 问题描述 给定一个字符串 s判断它是否是有效的括号序列。有效的括号序列需要满足以下条件 左括号必须有对应的右括号与之配对。括号必须按照正确的顺序配对。 括号包括圆括号 ()、方括号 [] 和花括号 {}。 解题思路 使用栈结构栈是一种后进先出LIFO的数据结构非常适合处理配对问题。遍历字符串逐个字符遍历字符串 s。遇到左括号如果是左括号(, [, {则将其推入栈中。遇到右括号如果是右括号), ], } 检查栈顶是否有对应的左括号 如果栈为空或者栈顶元素与当前右括号不匹配说明括号序列无效返回 False。如果匹配将栈顶元素弹出。 遍历结束遍历完成后检查栈是否为空 如果栈为空说明所有括号都正确配对返回 True。如果栈不为空说明有未配对的左括号返回 False。 c demo
#include iostream
#include stack
#include string
#include mapusing namespace std;class Solution {
public:bool isValid(string s) {stackchar st;// 定义括号的映射关系mapchar, char brackets { {), (}, {], [}, {}, {} };for (char c : s) {if (c ( || c [ || c {) {// 如果是左括号压入栈中st.push(c);}else {// 如果栈为空或者栈顶元素与当前右括号不匹配返回falseif (st.empty() || brackets[c] ! st.top()) {return false;}// 匹配则弹出栈顶元素st.pop();}}// 如果栈为空则所有括号都正确配对return st.empty();}
};int main() {Solution solution;// 测试用例string test1 ();string test2 ()[]{};string test3 (];string test4 ([)];string test5 {[()]}();// 执行测试并打印结果cout Test 1: (solution.isValid(test1) ? True : False) endl;cout Test 2: (solution.isValid(test2) ? True : False) endl;cout Test 3: (solution.isValid(test3) ? True : False) endl;cout Test 4: (solution.isValid(test4) ? True : False) endl;cout Test 5: (solution.isValid(test5) ? True : False) endl;return 0;
}输出结果 Test 1: True Test 2: True Test 3: False Test 4: False Test 5: True 代码仓库地址isValid
