菜鸟笔记
提升您的技术认知

有效的括号-ag真人游戏

给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true

思路:这个题目很容易想到用栈来做,或者数组模拟栈

  1. 遍历数组将碰到‘(’,‘{’,‘[’中的某一种则将它入栈,
  2. 否则查看当前遍历的元素与栈顶元素是否匹配,如果不匹配则return false
  3. 如果匹配这栈顶元素出栈 ,如此直到末尾
  4. 最后遍历完后检查栈中是否存在元素,如果存在说明还有没有匹配的,return false
public static  boolean isvalid(string s) {
        stack stack = new stack<>();
        char[] st = s.tochararray();
        for (int i = 0; i < st.length; i  ) {
            char a = st[i];
            if('('==a||'{'==a||'['==a){
                stack.push(a);
            }else{
                if(stack.size()==0){
                    return false;
                }
                char tmp = (char) stack.pop();
                switch (a) {
                case ')':
                    if('('!=tmp){
                        return false;
                    }
                    break;
                case '}':
                    if('{'!=tmp){
                        return false;
                    }
                    break;
                case ']':
                    if('[' != tmp){
                        return false;
                    }
                    break;
                default:
                    return false;
                }
            }
        }
        if(stack.size()>0){
            return false;
        }
        return true;
    }

上述代码说实话很辣眼睛,一个更加优雅,看着都湿了的解法如下

  1. 层次更高,看的高,理的透啊
  2. 我们现在不把“(、{、[”入栈了,我们改为如果匹配到‘(’,则将‘)’入栈
    匹配到‘{’则入栈‘}’,‘[’入栈‘]’ ,如果是字符是 )} ] 中的一种则栈顶出栈,厉害厉害
    有点服,一时半会儿还真的想不出来可以这么玩。
public static  boolean isvalid1(string s) {
        stack stack = new stack();
        for(character c :s.tochararray()){
            switch (c) {
                case '(':
                    stack.push(')');
                    break;
                case '{':
                    stack.push('}');
                    break;
                case '[':
                    stack.push(']');
                    break;
                default:
                    if(stack.isempty() || stack.pop() !=c){
                        return false;
                    }
                    break;
            }
        }
        return stack.isempty();
    }
网站地图