1:有效的括号LeetCode(20)

2019-03-28  本文已影响0人  Spring_java

题目:

给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。

有效字符串需满足:

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

注意空字符串可被认为是有效字符串。

解题思路:

1:重点考虑4,必须一一对应才是正确的。

2:可以这么做,如果全部都是左边的符号,就保存进去,如果是右边符号,那么就先判断栈是不是空的,
如果是空的,就是返回false;
如果不是空的,就弹出数据,判断这个数据,和你的右边符号是不是对应,如果对应就是true,否则就是false。

代码:

    public static void main(String[] args) {
        boolean b = isValid("()[]{}");
        System.out.println(b);
        
    }
    
//  给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
    
//  这道题让我们验证输入的字符串是否为括号字符串,包括大括号,中括号和小括号。
//  这里我们需要用一个栈,我们开始遍历输入字符串,如果当前字符为左半边括号时,则将其压入栈中,
//  如果遇到右半边括号时,若此时栈为空,则直接返回false,
//  如不为空,则取出栈顶元素,
//  若为对应的左半边括号,则继续循环,反之返回false,
    
    public static boolean isValid(String s) {
        
        if(s.isEmpty()) {
            return true;
        }
        Stack<Character> stack=new Stack<Character>();
        for(int i=0;i<s.length();i++) {
            char ch = s.charAt(i);
            if(ch=='(' || ch=='{' || ch=='[') {
                stack.push(ch);
            }else {
                if(stack.isEmpty()) {
                    return false;
                }
                Character pop = stack.pop();
                if(ch=='('&&pop!=')') {
                    return false;
                }
                if(ch=='{'&&pop!='}') {
                    return false;
                }
                if(ch=='['&&pop!=']') {
                    return false;
                }
            }
        }
        return stack.isEmpty();
        
    }
if(s.isEmpty()) {
            return true;
        }
        Map<Character,Character> map=new HashMap<Character,Character>();
        map.put(')', '(');
        map.put('}', '{');
        map.put(']', '[');
        
        Stack stack=new Stack();
        for(int i=0;i<s.length();i++) {
            char temp = s.charAt(i);
            // 如果是左边括号,就放进去
            if(map.containsValue(temp)) {
                stack.push(temp);
                //如果包含右边的括号,就判断,取出来比较
            }else if(map.containsKey(temp)) {
                if(stack.isEmpty()) {
                    return false;
                }
                if(stack.peek()==map.get(temp)) {
                    stack.pop();
                }else {
                    return false;
                }
            }
            
        }
        return stack.isEmpty();
上一篇下一篇

猜你喜欢

热点阅读