游戏门户网站有哪些,wordpress发布pdf,南通注册公司,php网站开发说明【问题描述】[中等] 【解答思路】
1. 栈
如果是一个合法的括号序列#xff0c;遍历到一个右括号(i)时#xff0c;那么它的前一个括号(i-1)必定是它的另一半(左括号)。反之不是它的另一半或者前面没有括号时#xff0c;那这个序列必定是非法括号序列。 思路#xff1a;利用…【问题描述】[中等] 【解答思路】
1. 栈
如果是一个合法的括号序列遍历到一个右括号(i)时那么它的前一个括号(i-1)必定是它的另一半(左括号)。反之不是它的另一半或者前面没有括号时那这个序列必定是非法括号序列。 思路利用一个stack辅助保存括号遇见左括号时入栈对应的右括号遇到右括号时
栈空证明前面没有匹配括号 多余的右括号栈非空弹出栈顶元素进行比较操作 最后判断栈是否为空空 括号匹配非空 多余的左括号
要么在入栈时根据不同类别入栈右括号 要么出栈的时候根部不同类别作判断 至少进行一次分类讨论 时间复杂度O(N) 空间复杂度O(N)
优秀代码
class Solution {public boolean isValid(String s) {int len s.length();if (s null || len 0) return true;if (len % 2 ! 0) {// 如果长度为奇数必然至少有一个括号没有匹配return false;}DequeCharacter stack new ArrayDeque();for (char ch : s.toCharArray()) {if (ch () {stack.addLast());} else if (ch [) {stack.addLast(]);} else if (ch {) {stack.addLast(});} else if (stack.isEmpty() || stack.removeLast() ! ch) {return false;}}return stack.isEmpty();}
} public boolean isValid(String s) {if(s.isEmpty())return true;StackCharacter stacknew StackCharacter();int n s.length();for(int i 0;in;i){char a s.charAt(i);if(a()stack.push());else if(a{)stack.push(});else if(a[)stack.push(]);else{if(stack.isEmpty()||stack.pop()!a ){return false;}}}return stack.isEmpty();}借助栈对字符串进行字符遍历如果字符是左括号则入栈左括号为’(’’{’’[’如果字符是右括号则出栈并将右括号与左括号联合比较判断是否可以组成有效的括号有效括号是(){}[]如果不能组成则返回错误
class Solution {public boolean isValid(String s) {StackCharacter stack new Stack();for (int i 0; i s.length(); i) {char c s.charAt(i);if (c { || c ( || c [) {stack.push(c);} else {char p stack.empty() ? \0 : stack.pop();if ((c } p ! {) || (c ] p ! [)|| (c ) p ! ()) {return false;}}}return stack.empty();}
}
2. HashMap
时间复杂度O(N) 空间复杂度O(1)
public boolean isValid(String s) {if (s null) {// 如果输入字符为空没有必要继续下去直接返回falsereturn false;}int len s.length();if (len % 2 ! 0) {// 如果长度为奇数必然至少有一个括号没有匹配return false;}MapCharacter, Character pairs new HashMap();pairs.put(), ();pairs.put(], [);pairs.put(}, {);DequeCharacter stack new LinkedList();for (int i 0; i len; i) {char current s.charAt(i);if (pairs.containsKey(current)) {// 如果栈已经为空了说明右括号比左括号多不匹配直接返回false// 当第一次出现右括号的时候 栈顶元素必然为左括号不然不匹配直接返回falseif (stack.isEmpty() || stack.peek() ! pairs.get(current)) {return false;}stack.pop();} else {stack.push(current);}}// 如果最后栈不为空说明左括号多于右括号不匹配返回falsereturn stack.isEmpty();
}
【总结】
1. 优化
1.1 判断长度为奇数时 直接返回错误 1.2 使用Deque 代替 stack stack在基于数组实现上效率低 扩容效率低
初始化
DequeCharacter stack new ArrayDeque();
DequeCharacter stack new LinkedList();1.3 字符串转z字符数组遍历 速度较快
String s;
char[] chs.toCharArray()2.Deque 参考文章https://www.cnblogs.com/lxyit/p/9017350.html
