LeetCode20_Valid Parentheses有效的括号(栈相关问题)
2024-08-29 07:53:13
题目:
给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路:
使用栈这个数据结构;
Java实现:
import java.util.Stack; class Solution {
public boolean isValid(String s) { Stack<Character> stack = new Stack<>();
for (int i = 0; i<s.length(); i++){
char c = s.charAt(i);
if(c == '('||c == '['|| c == '{')
stack.push(c);
else{
if(stack.isEmpty())
return false;
char topChar = stack.pop();
if(c==')'&& topChar != '(')
return false;
if(c==']'&& topChar != '[')
return false;
if(c=='}'&& topChar != '{')
return false;
}
}
return stack.isEmpty();
}
}
C++实现:
class Solution {
public:
bool isValid(string s) {
stack<char> sk;
for(int i = ; i<s.size();i++)
{
//一旦遇到左括号,就压栈
if(s[i]=='[' || s[i]=='(' || s[i]=='{')
sk.push(s[i]);
else
{
//对于只包括各种括号的字符串,如果在此处栈为空
//则必然出现) ] }先于 ( [ {出现的情况,则为false
if(sk.empty())
return false;
// 进行括号匹配,一旦和栈顶不匹配,就返回false
if(s[i]==')' && sk.top()!='(')
return false;
if(s[i]==']' && sk.top()!='[')
return false;
if(s[i]=='}' && sk.top()!='{')
return false;
// 栈顶匹配,出栈
sk.pop();
}
}
//保证栈为空,同时涵盖空字符串的情况
return sk.empty();
}
};
最新文章
- JDBC——Java代码与数据库链接的桥梁
- 重温Servlet学习笔记--request对象
- C#中AppDomain.CurrentDomain.BaseDirectory及各种路径获取方法
- struts2+spring+hibernte整合示例
- :nth-child
- 深入浅出设计模式——抽象工厂模式(Abstract Factory)
- yii框架中保存第三方登录信息
- linux入门教程(二) 图形界面还是命令窗口
- Codeforces Round #240 (Div. 2)(A -- D)
- LINUX进程优先级实现
- 信号之system函数
- Ubuntu16.04下Intellij IDEA不能输入中文的问题
- 认识ExtJS(05)--
- [bzoj1592] Making the Grade
- java实现最小生成树的prim算法和kruskal算法
- Instrumentation(1)
- JS去除掉字符串前后空格
- 使用LVM进行分区扩展的记录
- HIBERNATE与 MYBATIS的对比
- AangularJS的表单验证
热门文章
- Gulp和webpack的作用和区别
- python 异常处理与流程控制
- docker如何push镜像到docker hub个人的仓库
- 数组的查找,删除 Day07
- 当pip安装因为网络超时而无法安装的时候慢
- selenium webdriver学习(五)------------iframe的处理(转)
- 自定义element树表格图标
- Python3:ImportError: No module named &#39;compiler.ast&#39;
- libsvm的安装,数据格式,常见错误,grid.py参数选择,c-SVC过程,libsvm参数解释,svm训练数据,libsvm的使用详解,SVM核函数的选择
- ImportError: DLL load failed: 找不到指定的模块。 TensorFlow 1.13