括号匹配问题 —— Deque双端队列解法
2024-08-25 20:38:53
题目:
给定一个只包括 '(',')','{','}','[',']'?的字符串,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
思路:
我思路比较简单,就是从左往右看
如果是 "(" "{" "[" 这三个的话,直接进入队列中
如果遇到 ")" "}" "]" 这三个的话,就去看队列中的最后一个是不是和他匹配,如果是,那就移除最后一个,如果不是,那就直接跳出循环,肯定就不是一个合格的括号啦~(这时候队列里面还有没有匹配上的括号)
tips:可以在最开始加个判断,如果是奇数,就肯定是不合格的括号~
代码如下:
public static boolean isValid(String s) {
if (s.length() % 2 == 1) {
return false;
}
Map<String, String> map = new HashMap<String, String>();
map.put(")", "(");
map.put("}", "{");
map.put("]", "["); int i = 0;
Deque<String> queue = new LinkedList<String>();
while(i < s.length()) {
String now = s.substring(i, i+1);
if (!queue.isEmpty() && map.containsKey(now)) {
if (queue.getLast().equals(map.get(now))) {
queue.removeLast();
} else {
break ;
} } else {
queue.offer(now);
}
i++;
} if (queue.isEmpty()) {
return true;
} else {
return false;
}
}
最新文章
- ReactNative新手学习之路03真机调试
- http gzip 解压缩
- Squid 操作实践
- 设计模式:简单工厂(Simple Factory)
- java安全令牌生成器
- HTML5学习笔记三:aside元素,time元素与微格式
- 在react.js上使用antd-design没有样式
- 入门vue----(介绍)
- 【Android】Android WebView 网页输入框获取焦点
- SSH框架学习------struts2(一)
- OpenGL纹理
- python-中介者模式
- 【colaboratory】在colab中安装mxnet
- python list数据写入文件
- mysql ssh 端口转发
- linux 重新设置memsql密码
- [AIR] StageWebView可以和js通信
- Android——通知 Notification
- PIE SDK元素的删除
- es6+最佳入门实践(7)
热门文章
- Springboot配置文件获取系统环境变量的值
- 【转载】 十图详解tensorflow数据读取机制(附代码)
- python中异常处理之esle,except,else
- MyBatis-Spring项目
- 【计算机视觉】OpenCV篇(4) - Pycharm+PyQt5+Python小项目实战
- curl命令测试网络请求中DNS解析、响应时间
- IE11的变化 navigator.userAgent中不再包含“MSIE”关键字
- Linux下,postgreSQL的查看与重启
- Selenium登录126邮箱,chrome定位不到账号输入框解决办法
- web端自动化——selenium3+Python3+pycharm自动化