LeetCode-有效的括号(java实现) 爱被打了一巴掌 2022-05-18 09:55 125阅读 0赞 题目如下: ![70][] 刚看到这题的时候,还是非常简单的想暴力解决。暴露了眼界还是太狭隘。刚开始的想法是只要判断出"()\{\}\[\]"、"(\{\[\]\})"、"()"...等这样为true的情况应该就能解决问题了。但是想法太简单 ,运行的结果不是忘了判断这种情况就是忘了判断那种情况,最后运算还超时了。 后来在网上找了一下代码,运行时间为14ms。这段代码运用了栈stack,这是以前的知识盲区。整体的思路是这样的:例如我们需要判断如下字符串“\{\[\]\}”,把字符串的第一个字符压入栈,然后用字符串的后一个字符与之相比较。如果不相同,则把这个字符也压入栈。第二次for循环,此时stack.peek()取到的是‘\[’, s.charAt(i) == '\]'。此时根据if中的判断条件,表达式为true,stack把栈顶元素弹出。此时stack中还剩下一个元素‘(’,进入下一次for循环,stack.peek()取值是')',再次进入循环判断。 代码如下: public boolean isValid(String s) { if(s == "" || s.length() == 0) return true; Stack stack = new Stack(); stack.push(s.charAt(0)); for(int i=1; i<s.length(); i++){ if(!stack.isEmpty()){ if(stack.peek().equals((char)(s.charAt(i)-1)) || stack.peek().equals((char)(s.charAt(i)-2))){ stack.pop(); }else { stack.push(s.charAt(i)); } }else { stack.push(s.charAt(i)); } } if(stack.isEmpty()) return true; return false; 运行成功之后,看到一个实现代码,同样是运用了stack。但是运行时间只有6ms,相差了快3倍。遂好好把玩了一番,不得感叹,喵啊~ 具体思路就不啰嗦了,代码表达的非常清晰 public boolean isValid(String s) { Stack<Character> stack = new Stack<>(); for (int i = 0; i < s.length(); i++){ char ch = s.charAt(i); if(ch == '(' || ch == '[' || ch == '{'){ stack.push(ch); }else{ if(stack.isEmpty()){ return false; } char topChar = stack.pop(); if(ch == ')' && topChar != '('){ return false; }else if(ch == ']' && topChar != '['){ return false; }else if(ch == '}' && topChar != '{'){ return false; } } } return stack.isEmpty(); } [70]: /images/20220518/b5c0d67e20724ca1900afbf9531fe468.png
还没有评论,来说两句吧...