2020-11-1 有效的括号【简单题20】

题目

解题

【思路】

对于对称括号这种问题，我们很容易想到用栈解决。
当括号是左括号时，入栈；当括号是右括号时，判断其是否与栈顶的左括号匹配，是，栈顶元素出栈，继续判断下一个，否，返回false。

【代码1】

class Solution {
    public boolean isValid(String s) {
        Stack stack = new Stack();
        for(int i=0; i<s.length(); i++){
            if(s.charAt(i)=='('||s.charAt(i)=='['||s.charAt(i)=='{')  //左括号，入栈
                stack.push(s.charAt(i));
            else{  //右括号，判空
                if(!stack.empty())  //栈非空，判断是否匹配
                {
                    switch(s.charAt(i)){   //没用哈希表，因为括号类型就3种
                        case ')':
                            if((char)stack.peek()=='(')
                                stack.pop();
                            else return false;
                            break;
                        case ']':
                            if((char)stack.peek()=='[')
                                stack.pop();
                            else return false;
                            break;
                        case '}':
                            if((char)stack.peek()=='{')
                                stack.pop();
                            else return false;
                            break;
                        default:
                            break;
                    }
                }
                else
                    return false;
            }

        }
        if(stack.empty())
            return true;
        else
            return false; 
    }
}

【代码2】

class Solution {
    public boolean isValid(String s) {
        LinkedList<Character> stack = new LinkedList<>();
        for (char c : s.toCharArray()) {
            if (c == '[') stack.push(']');
            else if (c == '(') stack.push(')');
            else if (c == '{') stack.push('}');
            else if (stack.isEmpty() || c != stack.pop()) return false;
        }
        return stack.isEmpty();
    }
}

【改进】

class Solution {
    public boolean isValid(String s) {
        int n = s.length();
        if (n % 2 == 1) {  //非偶数，不对称
            return false;
        }

        Map<Character, Character> pairs = new HashMap<Character, Character>() {{  //用了哈希
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};
        Deque<Character> stack = new LinkedList<Character>();
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if (pairs.containsKey(ch)) {  //右括号
                if (stack.isEmpty() || stack.peek() != pairs.get(ch)) { //空栈或者不匹配，false
                    return false;
                }
                stack.pop();  //否则，出栈
            } else {  //左括号，入栈
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }
}

/*作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/valid-parentheses/solution/you-xiao-de-gua-hao-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。/*

【总结】

代码1和代码2没用哈希表，当时考虑括号只给了3个类型，就直接switch…if了。如果为了使程序可扩展性更强的话，应该用官方代码：哈希表。

知识总结

1. 栈和队列：
   Stack,Deque,Queue对比
   
   
   为什么使用Deque而不使用Stack构造栈
   

2. 创建栈
   Stack stack = new Stack();
   LinkedList stack = new LinkedList<>();
   Deque stack = new LinkedList();

3. 入栈
   stack.push(’]’);

4. 查看栈顶元素
   stack.peek();

5. 返回栈顶元素，并将其出栈
   stack.pop();

6. 判断栈顶是否为空
   stack.isEmpty();