作者:Grey
原文地址:LeetCode 20. Valid Parentheses
题目描述题目链接
思路- 遇到左括号入栈
- 遇到右括号,从栈里先d出一个元素,如果d出的元素和这个右括号正好匹配,则继续,如果不匹配,直接返回不是合法序列
走完整个遍历后,栈为空,则是合法序列,栈不为空,则不是合法序列。
在遍历过程中(还没遍历结束),一旦某个时间点栈为空,则直接返回不合法序列。
完整源码:
public static boolean isValid(String s) { if (s == null || s.length() == 0) { return true; } char[] strs = s.toCharArray(); Dequestack = new ArrayDeque (); int len = strs.length; for (int i = 0; i < len; i++) { if (isLeft(strs[i])) { stack.push(strs[i]); } else { if (stack.isEmpty()) { // 遍历的中间过程,一旦发现栈空,则直接返回false return false; } else if (!isMatch(stack.poll(), strs[i])) { return false; } } } return stack.isEmpty(); } public static boolean isLeft(char c) { return '(' == c || '{' == c || '[' == c; } public static boolean isMatch(char left, char right) { return (left == '[' && right == ']') || (left == '(' && right == ')') || (left == '{' && right == '}'); }
注:这里没有使用stack,而是用的Deque,原因在这里:Java Deque vs. Stack
We’ve seen that the Stack class is a subclass of java.util.Vector. The Vector class is synchronized. It uses the traditional way to achieve thread-safety: making its methods “synchronized.” As its subclass, the Stack class is synchronized as well. On the other hand, the Deque interface is not thread-safe.So, if thread-safety is not a requirement, a Deque can bring us better performance than a Stack.
简言之,Deque使用无锁 *** 作,线程不安全,但是效率更高,如果不要求线程安全,Deque是更好的选择。
更多算法和数据结构笔记
参考资料- Java Deque vs. Stack
- 程序员代码面试指南(第2版)
- 算法和数据结构基础班-左程云
- 极客时间-数据结构与算法之美-王争
- 算法(第四版)
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)