怎么进网站,凡客网站建站教程,城市规划做底图的网站,最好用的磁力搜索神器用来熟悉一下栈的应用之括号匹配 题目链接
下面是大致思路 1.初始化:创建一个空栈,用于存储左括号。#xff08;LC这题不用#xff0c;自己写完整的需要#xff09; 2.遍历字符串:从左到右依次扫描字符串中的每个字符。 3.处理左括号:如果是左括号,将其压入栈中。 4.处理右… 用来熟悉一下栈的应用之括号匹配 题目链接
下面是大致思路 1.初始化:创建一个空栈,用于存储左括号。LC这题不用自己写完整的需要 2.遍历字符串:从左到右依次扫描字符串中的每个字符。 3.处理左括号:如果是左括号,将其压入栈中。 4.处理右括号:如果是右括号,检查找顶元素是否与其匹配:
如果匹配,弹出栈顶元素。如果不匹配,返回false,表示括号不匹配。
5.检查栈是否为空:
遍历结束后,检查找是否为空。如果栈为空,表示所有括号匹配;否则,返回false。 还有就是一开始可以直接排除掉奇数个的情况不可能匹配
可运行版
下面就是注意一个地方
pairs函数在扫描的时候如果发现是左括号那么会进入后面的else逻辑让左括号入栈 如果发现是右括号 那么会返回与之匹配的左括号去和当前栈顶的左括号匹配
#include stdio.h
#include stdlib.h
#include stdbool.h
#include string.h// 定义一个函数 pairs用于返回与右括号对应的左括号
char pairs(char a)
{if (a })return {;if (a ])return [;if (a ))return (;return 0;
}// 检查括号是否匹配的函数
bool isValid(char *s)
{int n strlen(s); // 获取字符串的长度if (n % 2 1){ // 如果字符串长度是奇数不可能匹配return false;}int *stk (int *)malloc((n 1) * sizeof(int)); // 动态分配栈的大小if (stk NULL){printf(Memory allocation failed\n);return false;}int top 0; // 初始化栈顶指针int i; // 将变量声明移到循环外部for (i 0; i n; i){char ch pairs(s[i]); // 获取与当前字符对应的左括号if (ch){ // 如果当前字符是右括号if (top 0 || stk[top - 1] ! ch){ // 检查栈是否为空或栈顶元素是否匹配free(stk); // 释放动态分配的内存return false;}top--; // 弹出栈顶元素}else{ // 如果当前字符是左括号stk[top] s[i]; // 将左括号压入栈中}}bool result (top 0); // 如果栈为空表示所有括号匹配free(stk); // 释放动态分配的内存return result;
}// 示例使用
int main()
{printf(%d\n, isValid(())); // 输出: 1 (true)printf(%d\n, isValid(()[]{})); // 输出: 1 (true)printf(%d\n, isValid((])); // 输出: 0 (false)printf(%d\n, isValid(([)])); // 输出: 0 (false)printf(%d\n, isValid({[]})); // 输出: 1 (true)// 复杂的例子printf(%d\n, isValid({[()]})); // 输出: 1 (true)printf(%d\n, isValid({[(])})); // 输出: 0 (false)printf(%d\n, isValid({{[[(())]]}})); // 输出: 1 (true)return 0;
}
cpp #include iostream
#include stack
#include string
using namespace std;
class Solution
{
public:bool isMatch(char a, char b){if ((a ( b )) || (a [ b ]) || (a { b })){return true;}return false;}bool isValid(string s){stackchar stk; // 定义一个栈用来存放左括号// stack是一个容器适配器它提供了一种先进后出的数据结构即栈。只能在栈顶进行插入和删除操作。if (s.size() % 2 1)return false; // 如果字符串长度为奇数则不可能有效直接返回falsefor (int i 0; i s.size(); i){ // 扫描字符串遇到左括号入栈遇到右括号则与栈顶元素匹配if (s[i] ( || s[i] [ || s[i] {)stk.push(s[i]); // 遇到左括号入栈// 下面的两个else if 和 else都是对右括号情况的处理else if (stk.empty())return false; // 如果遇到了右括号但是栈已经空了说明不是有效的括号,直接返回false;else if (!isMatch(stk.top(), s[i]))return false; // 如果遇到右括号且栈不为空但是栈顶不是相匹配的左括号返回false;elsestk.pop(); // 当前遍历到的右括号与栈顶左括号相匹配弹出栈顶元素继续遍历}return stk.empty(); // 遍历结束后栈为空则为有效否则无效}
};int main()
{Solution s;cout s.isValid(()) endl; // 输出: 1 (true)cout s.isValid(()[]{}) endl; // 输出: 1 (true)cout s.isValid((]) endl; // 输出: 0 (false)return 0;
}LC版
C版 注意 两个empty的不同 比如具体的例子如下 class Solution {
public:bool isMatch(char a,char b){if(a ( b ) ||a [ b ]||a { b })return true;elsereturn false;}bool isValid(string s) {int n s.size();if (n % 2 1) {return false;}stackchar stk;for(int i 0; i n ; i){if(s[i]( || s[i][ || s[i]{ )stk.push(s[i]);else if(stk.empty())return false;else if(!isMatch(stk.top(),s[i]))return false;else if(isMatch(stk.top(),s[i]))stk.pop();}return stk.empty(); // 遍历结束后栈为空则为有效否则无效}};
C版
char pairs(char a) {if (a }) return {;if (a ]) return [;if (a )) return (;return 0;
}bool isValid(char* s) {int n strlen(s);if (n % 2 1){return false;}int stk[n 1], top 0;for (int i 0; i n; i){char ch pairs(s[i]);if(ch) // 如果是右括号{if ( top 0 || stk[top - 1] ! ch) {// 如果是空栈或者不匹配return false;}top --; // 匹配了就要出栈了top--指向新的位置}else //如果是左括号就入栈{//一开始top是0那么先赋值再移动指针指向下一个位置stk[top] s[i];top;}}return top 0; //最后应该都出栈了
}//总结其实就是把哪些不成立的条件先列出来还有注意各种边界条件然后理解了算法原理就能写出代码了
