jjzjj

leetcode 20. Valid Parentheses 有效的括号(中等)

okokabcd 2023-03-28 原文

一、题目大意

标签: 栈和队列

https://leetcode.cn/problems/valid-parentheses

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

有效字符串需满足：

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

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

示例 4：

输入：s = "([)]"
输出：false

示例 5：

输入：s = "{[]}"
输出：true

提示：

  • 1 <= s.length <= 104
  • s 仅由括号 '()[]{}' 组成

二、解题思路

思路：括号匹配是典型的使用栈来解决的问题。从左向右遍历，每当遇到左括号便放入栈内，遇到右括号则判断其和栈顶的括号是否是统一类型，是则从栈内取出左括号，否则说明字符不串不合法。

实现：遍历字符串，如果栈为空则将当前字符入栈，如果栈顶字符与当前字符匹配则栈顶字符出栈，不匹配当前字符入栈，遍历结束如果栈为空说明字符串合法。

三、解题方法

3.1 Java实现

public class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (Character c : s.toCharArray()) {
            if (isPush(stack, c)) {
                stack.push(c);
            } else {
                stack.pop();
            }
        }
        return stack.isEmpty();
    }

    private boolean isPush(Stack<Character> stack, Character c) {
        if (stack.isEmpty()) {
            return true;
        }

        // {[(
        boolean isPop = (stack.peek().equals('[') && c.equals(']') ||
                stack.peek().equals('{') && c.equals('}') ||
                stack.peek().equals('(') && c.equals(')'));
        return !isPop;
    }
}

3.2 2014年的实现

public class Solution {
    public boolean isValid(String s) {
        if (s == null || s.length() == 0) {
            return true;
        }
        Stack<Byte> ps = new Stack<Byte>();
        byte[] bArr = s.getBytes();
        boolean isValid = true;
        for (byte b : bArr) {
            if (!isValid) {
                break;
            }
            switch (b) {
            case '(':
            case '[':
            case '{':
                ps.push(b);
                break;
            case ')':
            case ']':
            case '}':
                if (!ps.empty()) {
                    byte tmpB = ps.pop();
                    if (tmpB == 40) {
                        tmpB++;
                    } else {
                        tmpB+=2;
                    }
                    if (tmpB != b) {
                        isValid = false;
                    }
                } else {
                    isValid = false;
                }
                break;
            default:
                // do nothing
            }
        }
        if (!ps.empty()) {
            isValid = false;
        }
        return isValid;        
    }
}

四、总结小记

  • 2022/8/9 一场秋雨一场寒
Parenthesesleetcodeblockquotestrongstack算法与数据结构

有关leetcode 20. Valid Parentheses 有效的括号(中等)的更多相关文章

  1. ruby - 如何进行排列以有效地定制输出 - 2

    这是一道面试题，我没有答对，但还是很好奇怎么解。你有N个人的大家庭，分别是1,2,3,...,N岁。你想给你的大家庭拍张照片。所有的家庭成员都排成一排。“我是家里的friend，建议家庭成员安排如下:”1岁的家庭成员坐在这一排的最左边。每两个坐在一起的家庭成员的年龄相差不得超过2岁。输入:整数N，1≤N≤55。输出:摄影师可以拍摄的照片数量。示例->输入:4，输出:4符合条件的数组:[1,2,3,4][1,2,4,3][1,3,2,4][1,3,4,2]另一个例子:输入:5输出:6符合条件的数组:[1,2,3,4,5][1,2,3,5,4][1,2,4,3,5][1,2,4,5,3][

  2. kvm虚拟机安装centos7基于ubuntu20.04系统 - 2

    需求：要创建虚拟机，就需要给他提供一个虚拟的磁盘，我们就在/opt目录下创建一个10G大小的raw格式的虚拟磁盘CentOS-7-x86_64.raw命令格式：qemu-imgcreate-f磁盘格式磁盘名称磁盘大小qemu-imgcreate-f磁盘格式-o?1.创建磁盘qemu-imgcreate-fraw/opt/CentOS-7-x86_64.raw10G执行效果#ls/opt/CentOS-7-x86_64.raw2.安装虚拟机使用virt-install命令，基于我们提供的系统镜像和虚拟磁盘来创建一个虚拟机，另外在创建虚拟机之前，提前打开vnc客户端，在创建虚拟机的时候，通过vnc

  3. Python 刷Leetcode题库，顺带学英语单词（31） - 2

    ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem

  4. python - 是否可以使用 Ruby 或 Python 禁用 anchor /引用来发出有效的 YAML？ - 2

    是否可以在PyYAML或Ruby的Psych引擎中禁用创建anchor和引用(并有效地显式列出冗余数据)？也许我在网上搜索时遗漏了一些东西，但在Psych中似乎没有太多可用的选项，而且我也无法确定PyYAML是否允许这样做.基本原理是我必须序列化一些数据并将其以可读的形式传递给一个不是真正的技术同事进行手动验证。有些数据是多余的，但我需要以最明确的方式列出它们以提高可读性(anchor和引用是提高效率的好概念，但不是人类可读性)。Ruby和Python是我选择的工具，但如果有其他一些相当简单的方法来“展开”YAML文档，它可能就可以了。 最佳答案

  5. ruby - 带括号和 splat 运算符的并行赋值 - 2

    我明白了:x,(y,z)=1,*[2,3]x#=>1y#=>2z#=>nil我想知道为什么z的值为nil。 最佳答案 x,(y,z)=1,*[2,3]右侧的splat*是内联扩展的，所以它等同于:x,(y,z)=1,2,3左边带括号的列表被视为嵌套赋值，所以它等价于:x=1y,z=23被丢弃，而z被分配给nil。 关于ruby-带括号和splat运算符的并行赋值，我们在StackOverflow上找到一个类似的问题： https://stackoverflow

  6. Ruby 正则表达式匹配逗号，但忽略括号中的逗号 - 2

    我正在尝试通过正则表达式拆分参数列表。这是一个带有我的参数列表的字符串:"a=b,c=3,d=[1,3,5,7],e,f=g"我想要的是:["a=b","c=3","d=[1,3,5,7]","e","f=g"]我试过先行，但Ruby不允许使用动态范围后行，所以这行不通:/(?如何让正则表达式忽略方括号中的所有内容？ 最佳答案 也许这样的东西对你有用:str.scan(/(?:\[.*?\]|[^,])+/)编辑再三考虑。简单的非贪婪匹配器在某些嵌套括号的情况下会失败。 关于Ruby正则

  7. ruby - 如何在ruby中提取方括号内的内容 - 2

    我正在尝试提取方括号内的内容。到目前为止，我一直在使用它，它有效，但我想知道我是否可以直接在正则表达式中使用某些东西，而不是使用这个删除功能。a="Thisissuchagreatday[coolawesome]"a[/\[.*?\]/].delete('[]')#=>"coolawesome" 最佳答案 差不多。a="Thisissuchagreatday[coolawesome]"a[/\[(.*?)\]/,1]#=>"coolawesome"a[/(?"coolawesome"第一个依赖于提取组而不是完全匹配；第二个利用前瞻和

  8. ruby - 为什么这个救援语法有效？ - 2

    好的，所以我有了我正在使用的应用程序的这种方法，它可以在生产中使用。我的问题为什么这行得通？这是新的Ruby语法吗？defeditload_elements(current_user)unlesscurrent_user.role?(:admin)respond_todo|format|format.json{render:json=>@user}format.xml{render:xml=>@user}format.htmlendrescueActiveRecord::RecordNotFoundrespond_to_not_found(:json,:xml,:html)end

  9. ruby - 奇怪的 ruby​​ for 循环行为(为什么这样做有效) - 2

    defreverse(ary)result=[]forresult[0,0]inaryendresultendassert_equal["baz","bar","foo"],reverse(["foo","bar","baz"])这行得通，我想了解原因。有什么解释吗？ 最佳答案 如果我使用each而不是for/in重写它，它看起来像这样:defreverse(ary)result=[]#forresult[0,0]inaryary.eachdo|item|result[0,0]=itemendresultendforainb基本上就

  10. arrays - 在两个数组中查找不相交元素的有效方法是什么？ - 2

    我有以下数组:A=[1,2,3,4,5]B=[2,6,7,1]我想找到不相交的元素，如下:output=[3,4,5,6,7]我是这样实现的，output=A+B-(A&B)但它效率低下，因为我添加了两个数组，然后删除了公共(public)元素。它类似于查找不相交的元素。我能做得比这更好吗？如果是，怎么办？ 最佳答案 如何只选择A中的元素而不是B中的元素以及B中的元素而不是A中的元素。(A-B)+(B-A) 关于arrays-在两个数组中查找不相交元素的有效方法是什么？，我们在Stack

随机推荐