20. Valid Parentheses

OA:
class Solution { public boolean isValid(String s) { char[] stack = new char[s.length()]; int head = 0; for (char c : s.toCharArray()) { if (c == '(') { stack[head++] = c; } else if (c == '[') { stack[head++] = c; } else if (c == '{') { stack[head++] = c; } else if (c == ')') { if (head == 0) return false; if (stack[--head] != '(') return false; } else if (c == ']') { if (head == 0) return false; if (stack[--head] != '[') return false; } else if (c == '}') { if (head == 0) return false; if (stack[--head] != '{') return false; } } return head == 0; } }
OA比MA快一倍。
String有个toCharArray()方法，返回一个装着该String的char[]。

 MA:
class Solution { public boolean isValid(String s) { Stack<Character> stack=new Stack<>(); for(int i=0;i<s.length();i++){ char temp=s.charAt(i); if(temp=='('||temp=='['||temp=='{') stack.push(temp); else if(temp=='}'&&!stack.empty()&&stack.peek()=='{'){ stack.pop(); continue; } else if(temp==']'&&!stack.empty()&&stack.peek()=='['){ stack.pop(); continue; } else if(temp==')'&&!stack.empty()&&stack.peek()=='('){ stack.pop(); continue; } else return false; } return stack.empty(); } }

评论

发表评论

此博客中的热门博文

225 Implement Stack using Queues

OA: class MyStack { Queue<Integer> queue; /** Initialize your data structure here. */ public MyStack () { queue = new LinkedList<>(); } /** Push element x onto stack. */ public void push ( int x) { queue.offer(x); int k = queue.size() - 1 ; while (k > 0 ) { queue.offer(queue.poll()); k--; } } /** Removes the element on top of the stack and returns that element. */ public int pop () { return queue.poll(); } /** Get the top element. */ public int top () { return queue.peek(); } /** Returns whether the stack is empty. */ public boolean empty () { return queue.isEmpty(); } } oa是push一次就逆序排一次（相当于每次push一个之后都把新push进去的那个排到最前面，这样下次pop的时候就是pop的这一个。） ma在top和pop的时候才把最后一个调到前面来，而且每次都要重新排。（感觉其实差不多，要看这个这个stack是pop和top用得多还是push用得多） MA: class MyStack { ArrayDeque<Integer> ...
阅读全文

232. Implement Queue using Stacks

MA: class MyQueue {     Stack<Integer> simQ=new Stack<Integer>();     Stack<Integer> buffer=new Stack<Integer>();     /** Initialize your data structure here. */     public MyQueue() {     }         /** Push element x to the back of queue. */     public void push(int x) {         simQ.push(x);     }         /** Removes the element from in front of queue and returns that element. */     public int pop() {         while(!simQ.empty()){             buffer.push(simQ.pop());         }         int temp=buffer.pop();         while(!buffer.empty()){             simQ.push(buffer.pop());         }         return temp;     } ...
阅读全文