尼采般地抒情

公告栏

此网站主题为本人手写主题,主题还在开发中……


作者:尼采般地抒情
本站主页面和blog页面暂时一样,目的是为了百度收录,百度收录之后,会将主页换回引导页~

站点信息

文章数目:195
已运行时间:
目录
  1. 问题思路
  2. 代码实现
    1. 栈实现
    2. HashMap 实现

尼采般地抒情

尼采般地抒情

公告栏

此网站主题为本人手写主题,主题还在开发中……


作者:尼采般地抒情
本站主页面和blog页面暂时一样,目的是为了百度收录,百度收录之后,会将主页换回引导页~

站点信息

文章数目:195
已运行时间:

问题思路

将所有的左半边括号 push 到栈内,然后遇到右半边括号,就将其与栈顶元素匹配测试,若能匹配成功则继续匹配,反之输出 false。

在这之间注意比较当栈内没有元素了,而字符串还有待匹配的字符,输出 false,当栈内还有元素,外面与之匹配测试的右半边括号,也输出 false。

代码实现

栈实现

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();

        int len = s.length();
        for (int i=0;i<len;i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) return false;
                char left = stack.pop();
                if (left == '(' && c !=')') return false;
                if (left == '[' && c !=']') return false;
                if (left == '{' && c !='}') return false;
            }
        }
        return stack.isEmpty();
    }
}
class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i< s.length();i++){
            if (s.charAt(0) == ')' || s.charAt(0) == ']' || s.charAt(0) == '}'){
                return false;
            }
            if (s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{'){
                stack.push(s.charAt(i));
            }
            if (s.charAt(i) == ')' || s.charAt(i) == ']' || s.charAt(i) == '}'){
                if (s.charAt(i) == ')'){
                    if (stack.isEmpty() == true) {
                        return false;
                    }
                    if (stack.pop() != '(')
                        return false;

                }
                if (s.charAt(i) == ']'){
                    if (stack.isEmpty() == true) {
                        return false;
                    }
                    if (stack.pop() != '[')
                        return false;

                }
                if (s.charAt(i) == '}'){
                    if (stack.isEmpty() == true) {
                        return false;
                    }
                    if (stack.pop() != '{')
                        return false;

                }
            }
        }
        if (stack.isEmpty() == true){
            return true;
        } else {
            return false;
        }

    }
}

HashMap 实现

class Solution {
    private static HashMap<Character, Character> map = new HashMap<>();
    static {
        // key - value
        map.put('(', ')');
        map.put('{', '}');
        map.put('[', ']');
    }

    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();

        int len = s.length();
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            if (map.containsKey(c)) { // 左括号
                stack.push(c);
            } else { // 右括号
                if (stack.isEmpty()) return false;

                if (c != map.get(stack.pop())) return false;
            }
        }
        return stack.isEmpty();
    }
}

博客内容遵循: 署名-非商业性使用-禁止演绎 4.0 国际(CC BY-NC-ND 4.0)

本文永久链接: https://www.wztlink1013.com/blog/aritwv/

编辑: 部署: 订阅:

评论区

Twikoo 转换 utterances

最新评论

Loading...