从小白开始刷算法 Stack 栈篇 leetcode.20

简介: 从小白开始刷算法 Stack 栈篇 leetcode.20

题目:


20.有效的括号


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


有效字符串需满足:


左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

每个右括号都有一个对应的相同类型的左括号。


示例 1:


输入:s = “()”

输出:true


示例 2:


输入:s = “()[]{}”

输出:true


题目来源:力扣(LeetCode)

能否写出:能写出来

时间:20分钟


思路:比较简单的一题,对初入门的学习stack友好,如果 c 是左括号字符 {, [, (,则将其对应的右括号字符 },],) 推入栈 stack 中,以便后续的匹配。

第一次写


class Solution {
    public static boolean isValid(String s) {
        if ("".equals(s)) return true;
        char[] chars = s.toCharArray();
        Stack<Character> stack = new Stack<>();
        boolean result = false;
        for (char c : chars) {
            switch (c) {
                case '{':
                    stack.push('}');
                    break;
                case '[':
                    stack.push(']');
                    break;
                case '(':
                    stack.push(')');
                    break;
                case ')':
                case ']':
                case '}':
                    if (stack.isEmpty()) return false;
                    result = stack.pop() == c;
                    //这里的操作有点繁琐了,后面要修改一下 尝试过return false也可以通过
                    if (!result) stack.push(c);
                    break;
                default:
                    return result;
            }
        }
        if (!stack.isEmpty()) {
            return false;
        }
        return result;
    }
}

第二版,简化


class Solution {
    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else if (c == ')' || c == ']' || c == '}') {
                if (stack.isEmpty()) {
                    return false;
                }
                char top = stack.pop();
                if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

网友Nakangzi,我觉得更好:


class Solution {
    public boolean isValid(String s) {
        Stack<Character>stack = new Stack<Character>();
        for(char c: s.toCharArray()){
            if(c=='(')stack.push(')');
            else if(c=='[')stack.push(']');
            else if(c=='{')stack.push('}');
            else if(stack.isEmpty()||c!=stack.pop())return false;
        }
        return stack.isEmpty();
    }
}

官方还有栈+map的解法


注意到有效字符串的长度一定为偶数,因此如果字符串的长度为奇数,我们可以直接返回 FalseFalse,省去后续的遍历判断过程。


时间复杂度:O(n)

空间复杂度:O(n)

空间的占用来自与stack的大小,随着字符串的长度增加,stack占用的空间会变大。

相关文章
|
3月前
|
算法
【算法】栈
栈相关算法题,供参考,附有链接地址及板书
|
4月前
|
存储 算法 Java
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
|
4月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
5月前
|
算法
每日一道算法题(Leetcode 20)
每日一道算法题(Leetcode 20)
55 2
|
5月前
|
缓存 算法 Java
JVM知识体系学习六:JVM垃圾是什么、GC常用垃圾清除算法、堆内存逻辑分区、栈上分配、对象何时进入老年代、有关老年代新生代的两个问题、常见的垃圾回收器、CMS
这篇文章详细介绍了Java虚拟机(JVM)中的垃圾回收机制,包括垃圾的定义、垃圾回收算法、堆内存的逻辑分区、对象的内存分配和回收过程,以及不同垃圾回收器的工作原理和参数设置。
215 4
JVM知识体系学习六:JVM垃圾是什么、GC常用垃圾清除算法、堆内存逻辑分区、栈上分配、对象何时进入老年代、有关老年代新生代的两个问题、常见的垃圾回收器、CMS
|
5月前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
89 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
5月前
|
算法
数据结构与算法二:栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式
这篇文章讲解了栈的基本概念及其应用,并详细介绍了中缀表达式转换为后缀表达式的算法和实现步骤。
106 3
|
5月前
【LeetCode 24】225.用队列实现栈
【LeetCode 24】225.用队列实现栈
28 0
|
5月前
|
算法
【LeetCode 23】232.用栈实现队列
【LeetCode 23】232.用栈实现队列
36 0
|
5月前
|
算法 C++
【算法单调栈】 矩形牛棚(C/C++)
【算法单调栈】 矩形牛棚(C/C++)

热门文章

最新文章