最近面试机会好少o(╯□╰)o，记录个笔试时的算法题

给定一个字符串所表示的括号序列，包含以下字符： '(', ')', '{', '}', '[' and ']'， 判定是否是有效的括号序列。括号必须依照 "()" 顺序表示， "()[]{}" 是有效的括号，但 "([)]"则是无效的括号。

补充：个人觉得出题人的本意是如"{[()]}"这种成对出现也是有效的。

分析1：有效的括号是成对的，我们定义一个方法将成对的括号转换成和为0的正负数，如 '(' 转换成-1，')'转换成1；

private int whatParentheses(char ch) {
        switch (ch) {
            case '(':
                return -1;
            case '[':
                return -2;
            case '{':
                return -3;
            case ')':
                return 1;
            case ']':
                return 2;
            case '}':
                return 3;
        }
        return 0;
    }

分析2：给出几个有效的 "( [ ] )" ，"( ) { }"，"[ { ( )}]"，可以看出第一个右括号的左边一定必须是它对应的左括号才有效。
得出一个解题思路：遍历字符串字符，如果是左括号那么我们用一个数据结构存起来，遇到第一个右括号时取数据结构中的最后一个数据，判断是否是对应的左括号。如果不是那么此序列是无效的，如果是那么我们把这一对括号移除掉（其实只是移除了最后一个左括号）再继续遍历。用栈Stack来实现可能比较理想，上代码。

private boolean isParenthesesValid(String s) {
        //字符串为空
        if (s==null){
            return false;
        }
        int length=s.length();
        Stack<Character> stack=new Stack<>();
        //存储遍历的字符
        char ch;
        //存储字符转换后的数字
        int parentNum;
        //记录下括号出现的次数
        int count=0；
        for (int i=0;i<length;i++){
            ch=s.charAt(i);
            parentNum=whatParent(ch);
            if(parentNum<0){
                count++;
               // <0表示这是个左括号
                stack.push(ch);
            }else if(parentNum>0){
                count++;
                // >0表示这是个右括号
                if (stack.isEmpty()){
                    //右括号左边没有左括号的特殊情况
                    return false;
                }
                if(parentNum+whatParent(stack.peek())==0){
                    //栈顶是对应的左括号
                    stack.pop();
                }else{
                    return false;
                }
             }else{
                // =0 这不是一个括号，不管
             }
        }
         //字符串中有括号且栈最后被清空了，表示括号成对出现且有效
        if (count > 0 && stack.isEmpty()){
            return true;
        }
        return false;
    }

参考：有效的括号序列（LintCode）

LintCode 挺有意思的，还可以检测代码风格O__O