LeetCode算法题 - 20. 有效的括号(栈实现c语言)
2021/11/26 1:10:42
本文主要是介绍LeetCode算法题 - 20. 有效的括号(栈实现c语言),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
20. 有效的括号
题目连接:https://leetcode-cn.com/problems/valid-parentheses/
难度:简单
给定一个只包括 ‘(’,’)’,’{’,’}’,’[’,’]’ 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
示例 1: 输入:s = "()" 输出:true 示例 2: 输入:s = "()[]{}" 输出:true 示例 3: 输入:s = "(]" 输出:false 示例 4: 输入:s = "([)]" 输出:false 示例 5: 输入:s = "{[]}" 输出:true
提示:
1 <= s.length <= 104
s 仅由括号 ‘()[]{}’ 组成
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
当遍历字符串遇到"{" "(" "["
就入栈 遇到 "]" ")" "}"
就和上一个括号进行匹配:
"}" -> "{"
"]" -> "["
")" -> "("
如果匹配成功,"{" "(" "["
就出栈,也就是top--
,类似消消乐,如果匹配失败则返回false
当所有字符的括号被遍历完,栈为空即top=0
则返回true
这里我是用一个数组做的栈,由于是用C语言写的,数组的大小并不能进行动态变化,所有需要提前定义一个较大的数组。
bool isValid(char * s){ int top = 0;//用来计栈的下标,进栈加1,出栈减1 int i = 0;//用来计字符的下标索引 int n = strlen(s);//计算字符长度 if (n % 2 == 1) {//字符串的括号的长度为奇数直接返回false return false; } int arr[n + 1];//用一个长度为字符串长度的数组定义栈 while (s[i]) { switch (s[i]) { case '(': case '[': case '{': arr[top] =s[i];//入栈 top++;//数组索引加1 break; case ')': if ( top < 1 || top >= 1 && arr[top-1] != '(' )//这里和上一个括号进行匹配,top < 1是栈已经为空没有括号可以进行对比,也直接返回false { return false; } top--;//出栈 break; case ']': if ( top < 1 || top >= 1 && arr[top-1] !='[') { return false; } top--; break; case '}': if( top < 1 || top >= 1 && arr[top-1] != '{') { return false; } top--; break; } i++; } return top == 0 ? true : false; }
这篇关于LeetCode算法题 - 20. 有效的括号(栈实现c语言)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-25TypeScript基础知识详解
- 2024-12-25安卓NDK 是什么?-icode9专业技术文章分享
- 2024-12-25caddy 可以定义日志到 文件吗?-icode9专业技术文章分享
- 2024-12-25wordfence如何设置密码规则?-icode9专业技术文章分享
- 2024-12-25有哪些方法可以实现 DLL 文件路径的管理?-icode9专业技术文章分享
- 2024-12-25错误信息 "At least one element in the source array could not be cast down to the destination array-icode9专业技术文章分享
- 2024-12-25'flutter' 不是内部或外部命令,也不是可运行的程序 或批处理文件。错误信息提示什么意思?-icode9专业技术文章分享
- 2024-12-25flutter项目 as提示Cannot resolve symbol 'embedding'提示什么意思?-icode9专业技术文章分享
- 2024-12-24怎么切换 Git 项目的远程仓库地址?-icode9专业技术文章分享
- 2024-12-24怎么更改 Git 远程仓库的名称?-icode9专业技术文章分享