leetcode刷题之

您所在的位置：网站首页 › 板烧鸡腿饭做法大全 › leetcode刷题之

leetcode刷题之

2023-06-01 12:07| 来源: 网络整理| 查看: 265

题目接口：

题目描述：

解释：

解题思路：

代码：

题目接口： bool isValid(char * s){ } 题目描述：

20. 有效的括号

难度简单

3929

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。解释：

这道题的意思就是符号匹配问题。当你的字符串内的左括号与右括号可以匹配的时候就可以返回true，否则返回false。比如字符串是："((( )))"，”（）[ ] { }"这样就返回true。如果是：“[ ] } }”,"(( ] ]"这样就返回false。等等……。从这些情况分析可以得出，如果你想用两个指针，一个从前往后，一个从后往前来一个一个匹配的话那就太难了，并且肯定是错的。但是我们现在有栈了，我们便可以根据栈的特点来做这道题。

解题思路：

栈的特点是后进先出，左右符号匹配的时候是用离得最近的左括号与右括号进行匹配的。现在，假如我让左括号入栈。当遇到右括号那就进行匹配那就可以实现离得最近的左括号与右括号进行匹配来判断对错！

代码：

第一步：

先写一个栈在题目中，因为我要使用C语言来写这道题目。所以我就要自己写一个栈来做题。

栈：myStack

代码：

typedef char DataType;//记得改为char型 typedef struct stack { int top; int capacity; DataType* a; }stack; void StackInit(stack* ST) { ST->capacity = 0;//栈的容量为0 ST->top = 0;//将top置为0表示现在的栈为空 ST->a = NULL;//将a初始化为为NULL } void PushStack(stack* ST, DataType x) { assert(ST); if (ST->top == ST->capacity)//当栈的容量满了就要扩容 { int newcapacity = ST->capacity == 0 ? 4 : 2 * ST->capacity; ST->a = (DataType*)realloc(ST->a, sizeof(DataType) * newcapacity); if (ST->a == NULL) { perror("realloc fail!"); return; } ST->capacity = newcapacity;//调整容量 } ST->a[ST->top] = x;//在top处插入数据 ST->top++; } bool StackEmpty(stack* ST) { return ST->top == 0;//当top指向0时栈就是一个空栈,返回true。 } void PopStack(stack* ST) { assert(ST); assert(!StackEmpty(ST)); ST->top--; } DataType TopStack(stack* ST) { assert(ST); return ST->a[ST->top - 1];//栈顶元素是top指向的上一个元素 } void StackDestory(stack* ST) {//将栈删空并将其中的元素置为NULL或0 assert(ST); free(ST->a); ST-> a = NULL; ST->capacity = 0; ST->top = 0; }

解题代码：

思路：左括号入栈，遇到右括号则出栈匹配！//保证右括号与最近的左括号进行匹配。

代码：

bool isValid(char * s){ stack ST ;//创建一个栈 StackInit(&ST);//初始化栈 while(*s!='\0') { if(*s == '('||*s == '{'||*s=='[')//左括号入栈 { PushStack(&ST,*s); } else { char top = '\0'; if(!StackEmpty(&ST)) { top = TopStack(&ST);//遇到右括号出栈匹配 PopStack(&ST);//出栈 } if((*s==')'&&top!='(')||(*s==']'&&top!='[')||(*s=='}'&& top!='{')) { return false;//匹配不上就返回false } } s++; } if(StackEmpty(&ST)) { return true;//当栈内元素都已匹配完成使栈变成空时才返回true,避免左括号数量多于右括号 } return false;//其它情况返回false }

【本文地址】

leetcode刷题之

leetcode刷题之

今日新闻

推荐新闻