LeetCode力扣每日一题(Java):20、有效的括号

2023-12-13 05:18:23

一、题目

二、解题思路

1、我的思路

我看到题目之后,想着这可能是力扣里唯一一道我能秒杀的题目了

于是一波操作猛如虎写出了如下代码

public boolean isValid(String s) {
        char[] c = s.toCharArray();
        for(int i=0;i<c.length;i++){
            switch (c[i]){
                case '(':
                    if(c[++i]!=')')
                        return false;
                    break;
                case '[':
                    if(c[++i]!=']')
                        return false;
                    break;
                case '{':
                    if(c[++i]!='}')
                        return false;
                    break;
            }
        }
        return true;
    }

运行的时候三个测试用例都通过了,我心想这把稳了。信心满满地点击提交……

什么?!解答错误

嗷,那没事了,原来左括号后不一定跟的是右括号……这就回去重写

再仔细一思考,猛然回想起当时学数据结构的时候遇到过的括号匹配问题。这可能要用到栈,遇到左括号就让这个左括号进栈,遇到右括号就出栈一个括号,如果这两个括号能匹配就继续执行,反之则直接返回false

于是有了如下的代码,而且这段代码的运行效率竟然击败了98%的用户

char[] sc = s.toCharArray();
        Stack<Character> stack = new Stack<>();
        for(int i=0;i<sc.length;i++){
            switch (sc[i]){
                case '(':
                case '{':
                case '[':
                    stack.push(sc[i]);
                    break;
                default:
                    if(stack.size()==0){
                        return false;
                    }
                    switch(stack.pop()){
                        case '(':
                            if(sc[i]!=')')
                                return false;
                            break;
                        case '{':
                            if(sc[i]!='}')
                                return false;
                            break;
                        case '[':
                            if(sc[i]!=']')
                                return false;
                            break;
                    }
            }
        }
        if(stack.size()!=0){
            return false;
        }
        return true;

?只不过我一开始没有考虑到循环中的

if(stack.size()==0){
    return false;
}

和循环结束的

if(stack.size()!=0){
    return false;
}

导致代码在测试 "[" 和 "]" 两个测试用例的时候都返回了错误的结果,还好力扣上可以看到出错的执行用例,所以我才能很快地找到问题

但是有很多算法竞赛是看不到执行出错的测试用例的,所以在打算法竞赛时,如果我们提交的代码出现了问题,不妨自己输入一些数据进行测试,而且要输入比较特殊的例子,如 "[" 和 "]" 这样的极端例子

2、官方题解

class Solution {
    public boolean isValid(String s) {
        int n = s.length();
        if (n % 2 == 1) {
            return false;
        }

        Map<Character, Character> pairs = new HashMap<Character, Character>() {{
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};
        Deque<Character> stack = new LinkedList<Character>();
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if (pairs.containsKey(ch)) {
                if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
                    return false;
                }
                stack.pop();
            } else {
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }
}

作者:力扣官方题解
链接:https://leetcode.cn/problems/valid-parentheses/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

三、栈

考虑到可能也有一些小伙伴不会用栈,在这里给大家科普一下(图片来源于《labuladong的算法笔记》)

文章来源:https://blog.csdn.net/lbcbjtlhmjq/article/details/134835103
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。