做一个自己的网站,网上商城建设多少钱,南京做网站的网络公司排名,网页棋牌搭建链接有效的括号题序号20题型字符串解法栈难度简单熟练度✅✅✅
题目
给定一个只包括 ‘(’#xff0c;‘)’#xff0c;‘{’#xff0c;‘}’#xff0c;‘[’#xff0c;‘]’ 的字符串 s #xff0c;判断字符串是否有效。
有效字符串需满足#xff1a; 左括号必须…链接有效的括号题序号20题型字符串解法栈难度简单熟练度✅✅✅
题目
给定一个只包括 ‘(’‘)’‘{’‘}’‘[’‘]’ 的字符串 s 判断字符串是否有效。
有效字符串需满足 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都有一个对应的相同类型的左括号。
示例 1 输入s “()” 输出true
示例 2 输入s “()[]{}” 输出true
示例 3 输入s “(]” 输出false
示例 4 输入s “([])” 输出true
提示 1 s.length 104 s 仅由括号 ‘()[]{}’ 组成
题解
核心思想判断括号是否有效关键在于匹配。我们需要确保每个左括号都能找到对应的右括号并且它们的顺序是正确的。为此可以使用栈Stack来实现。栈stack 栈是一种后进先出LIFO的数据结构适合处理括号匹配的问题。每当遇到左括号时将其压入栈中。每当遇到右括号时检查栈顶是否为匹配的左括号。 复杂度时间复杂度为O(n)其中 n 是字符串 s 的长度。空间复杂度为O(n)由栈的大小决定哈希表的空间是常数项因为常数项在大O表示法中是可以忽略的。这意味着算法的空间需求主要取决于输入数据的大小而与字符集的大小无关。c 实现算法
bool isValid(string s) {// 用栈保存未匹配的左括号stackchar st;// 使用哈希表存储括号的映射关系//键Key右括号包括 )、] 和 }。//值Value对应的左括号包括 (、[ 和 {。unordered_mapchar, char brackets {{), (},{], [},{}, {}};for (char c : s) {// 如果是右括号//在 unordered_map 中count(key) 用于检查给定的 键key 是否存在于哈希表中//如果 key 存在返回 1. 如果 键key 不存在返回 0if (brackets.count(c)) {// 栈顶字符与右括号的匹配//检查栈是否为空或者栈顶是否与当前右括号的匹配左括号相同//通过 brackets[c] 找到右括号对应的左括号如果 c 是 )brackets[c] 就是 (。if (!st.empty() st.top() brackets[c]) {st.pop(); // 匹配成功移除栈顶} else {return false; // 匹配失败}} else {// 如果是左括号入栈st.push(c);}}// 栈为空表示所有括号都匹配成功return st.empty();
}算法推演 以输入 s “{[()]}” 为例 遍历字符 ‘{’入栈 st [‘{’]。遍历字符 ‘[’入栈 st [‘{’, ‘[’]。遍历字符 ‘(’入栈 st [‘{’, ‘[’, ‘(’]。遍历字符 ‘)’ 栈顶为 ‘(’匹配成功弹出栈顶 st [‘{’, ‘[’]。遍历字符’]‘ 栈顶为 ‘[’匹配成功弹出栈顶 st [’{]。遍历字符 ‘}’ 栈顶为 ‘{’匹配成功弹出栈顶 st []。 遍历结束栈为空返回 true。 c 完整demo
#include iostream
#include stack
#include unordered_map
#include stringusing namespace std;bool isValid(string s) {// 用栈保存未匹配的左括号stackchar st;// 使用哈希表存储括号的映射关系//键Key右括号包括 )、] 和 }。//值Value对应的左括号包括 (、[ 和 {。unordered_mapchar, char brackets {{), (},{], [},{}, {}};for (char c : s) {// 如果是右括号//在 unordered_map 中count(key) 用于检查给定的 键key 是否存在于哈希表中//如果 key 存在返回 1. 如果 键key 不存在返回 0if (brackets.count(c)) {// 栈顶字符与右括号的匹配//检查栈是否为空或者栈顶是否与当前右括号的匹配左括号相同//通过 brackets[c] 找到右括号对应的左括号如果 c 是 )brackets[c] 就是 (。if (!st.empty() st.top() brackets[c]) {st.pop(); // 匹配成功移除栈顶} else {return false; // 匹配失败}} else {// 如果是左括号入栈st.push(c);}}// 栈为空表示所有括号都匹配成功return st.empty();
}int main() {string s {[()]};if (isValid(s)) {cout true endl;} else {cout false endl;}return 0;
}数据结构之 { 栈 }
数据结构中的栈Stack是一种遵循“后进先出”Last In First Out简称LIFO原则的有序集合。这意味着最后添加到栈中的元素会首先被移除。栈通常用于处理递归调用、函数调用、表达式求值、括号匹配等场景。栈的基本操作包括 压栈Push将一个元素添加到栈的顶部。弹栈Pop移除并返回栈顶部的元素。查看栈顶元素Peek 或 Top返回栈顶部的元素但不移除它。检查栈是否为空IsEmpty检查栈中是否有元素如果有返回false否则返回true。获取栈的大小Size返回栈中元素的数量。 栈可以用数组或链表来实现。数组实现的栈在空间上是连续的而链表实现的栈在空间上可以是非连续的。栈的应用场景 函数调用在函数调用时系统会将函数的参数、返回地址以及局部变量压入栈中函数执行完毕后这些信息会被弹栈。递归递归函数的每次调用都会创建一个新的栈帧用于存储局部变量和参数。括号匹配检查代码中的括号是否正确匹配可以使用栈来存储遇到的开括号并在遇到闭括号时检查是否匹配。表达式求值在计算表达式时可以使用栈来存储操作数和操作符以正确计算表达式的值。回溯算法在搜索和图算法中栈可以用来存储路径以便在需要时回溯到上一个状态。 栈是一种非常基础且重要的数据结构它在计算机科学和软件开发中有着广泛的应用。
