队列_LeetCode20题_有效的括号

题目描述

给定一个只包括’(’，’)’，’{’，’}’，’[’，’]'的字符串s，判断字符串是否有效。
有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。

解题思路

这道题乍一看想到了消消乐……三对括号一左一右两两成对，成对儿且相邻的俩括号能抵消掉，全抵消干净了这个字符串就有效了。但凡有相互嵌套的或者没抵消干净的，这个字符串就不是有效的。所以算法的思路应该大致如下：
从头遍历这个字符串，有啥符号记啥符号，然后如果某个符号跟上一个符号正好是一对儿，就把这俩符号消掉。如果消干净了，就返回true，遍历完之后依旧没消干净，那就不是有效队列了，返回false。
那么最容易实现这种数据结构的就是双端队列或者栈。因为Java中有双端队列的集合，直接用LinkedList蛮方便的。

class Solution {

    private LinkedList<Character> queue = new LinkedList<>();

    public boolean isValid(String s) {

        // 遍历整个字符串中的每一个字符
        for (int i = 0; i < s.length(); i++) {
            // 看看它是不是左括号，如果是左括号的话存到queue里
            if (isLeftBrackets(s.charAt(i))) {
                queue.addFirst(s.charAt(i));
            } else {
                // 走到这个分支表示当前字符是个右括号。如果queue是空的，那字符串必然无效，就不用继续了，直接false即可
                if (queue.isEmpty()) {
                    return false;
                }
                // 右括号出现的时候，它必然得跟上一个括号是匹配的。如果没匹配上，是个单出来的右括号，那字符串也必然无效
                if (isCorrectBrackets(s.charAt(i), queue.peekFirst())) {
                    queue.pollFirst();
                } else {
                    return false;
                }
            }
        }
        // 全部遍历完之后，如果队列是空的，说明所有括号两两抵消了，是有效的，否则就是无效的。
        if (queue.isEmpty()) {
            return true;
        } else {
            return false;
        }

    }

    private boolean isLeftBrackets(char c) {
        if (c == '(' || c == '[' || c == '{') {
            return true;
        } else {
            return false;
        }
    }

    private boolean isCorrectBrackets(char s, char queueElement) {
        if (s == ')' && queueElement == '(') {
            return true;
        }
        if (s == ']' && queueElement == '[') {
            return true;
        }
        if (s == '}' && queueElement == '{') {
            return true;
        }
        return false;
    }
}

此题得解。

一点优化思路

回过头想想，这种代码写法不是最优的，其实在这个思路上还可以做一些小优化：

1. 两个私有方法分别判断是不是成对的括号或者是不是左括号，逐个判断代码太冗余了。其实可以放到一个hashmap里头，判断是否是左括号可以查询有没有这个key；判断是不是一对儿括号可以通过key查询value，比对value是否相同。
2. 有效的字符串长度必为偶数，可以在最开始判断一下字符串的长度，如果是奇数那后面都不用运行了，直接false就可以。性能这东西省省没坏处。