草庐IT

LeetCode：20. 有效的括号——栈和队列

Super algorithm 2023-08-09 原文
🍎道阻且长，行则将至。🍓
🌻算法，不如说它是一种思考方式🍀


算法专栏： 👉🏻123

一、🌱20. 有效的括号

  • 题目描述：给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
    有效字符串需满足：
    左括号必须用相同类型的右括号闭合。
    左括号必须以正确的顺序闭合。
    每个右括号都有一个对应的相同类型的左括号。

  • 来源：力扣（LeetCode）

  • 难度：简单

  • 提示：
    1 <= s.length <= 104
    s 仅由括号 ‘()[]{}’ 组成

  • 示例 1：
    输入：s = “()”
    输出：true
    示例 2：
    输入：s = “()[]{}”
    输出：true
    示例 3：
    输入：s = “(]”
    输出：false

🌴解题

题目要求判断字符串是不是合法括号组合，也就是找到一个左括号，还要在后面有一个可以连接的有括号。这时候我们使用栈这种先进后出数据结构就很方便，当左括号进栈，只有匹配到下一个要进栈的是右括号，也就是找到一个匹配括号，将其弹出栈。而如果进栈一个不能弹出栈的右括号，这时候肯定括号存在交叉或者不匹配，可以提前退出返回false。只有当最后栈为空才返回true，否则返回false。

使用栈

为了熟悉栈，我们可以实现一个栈及其方法：

class MyStack {
    List<String> mystack=new ArrayList<>();
    public MyStack() {
    }
    public void push(String x) {//进栈
        mystack.add(x);
    }
    public String pop() {//弹出栈顶
        String x=mystack.get(mystack.size()-1);
        mystack.remove(mystack.size()-1);
        return x;
    }
    public String peek() {//栈顶
        return mystack.get(mystack.size()-1);
    }
    public boolean empty() {
        return mystack.isEmpty();
    }
}
  • code：
class Solution {
    public boolean isValid(String s) {
        MyStack stack=new MyStack();
        for (int i = 0; i < s.length(); i++) {
            if(!stack.empty()){//栈非空，就可以判断括号匹配
                switch(stack.peek()){
                    case "(":
                        if(s.charAt(i)==')')stack.pop();
                        else
                            stack.push(String.valueOf(s.charAt(i)));break;
                    case "[":
                        if(s.charAt(i)==']')stack.pop();
                        else
                            stack.push(String.valueOf(s.charAt(i)));break;
                    case "{":
                        if(s.charAt(i)=='}')stack.pop();
                        else
                            stack.push(String.valueOf(s.charAt(i)));break;
                    default:return false;
                }
            }else
            stack.push(String.valueOf(s.charAt(i)));
        }
        if(!stack.empty())
            return false;
        return true;
    }
}

行路难!行路难!多岐路，今安在?
长风破浪会有时，直挂云帆济沧海。

返回第一页。☝

☕物有本末，事有终始，知所先后。🍭

🍎☝☝☝☝☝我的CSDN☝☝☝☝☝☝🍓

mdashLeetCodespanclasstoken算法职场和发展

有关LeetCode：20. 有效的括号——栈和队列的更多相关文章

  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. ruby - 分布式事务和队列，ruby，erlang，scala - 2

    我有一个涉及多台机器、消息队列和事务的问题。因此，例如用户点击网页，点击将消息发送到另一台机器，该机器将付款添加到用户的帐户。每秒可能有数千次点击。事务的所有方面都应该是容错的。我以前从未遇到过这样的事情，但一些阅读表明这是一个众所周知的问题。所以我的问题。我假设安全的方法是使用两阶段提交，但协议(protocol)是阻塞的，所以我不会获得所需的性能，我是否正确？我通常写Ruby，但似乎Redis之类的数据库和Rescue、RabbitMQ等消息队列系统对我的帮助不大——即使我实现某种两阶段提交，如果Redis崩溃，数据也会丢失，因为它本质上只是内存。所有这些让我开始关注erlang和

  3. 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

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

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

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

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

  6. 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

  7. 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正则

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

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

  9. ruby-on-rails - Ruby 长时间运行的进程对队列事件使用react - 2

    我有一个将某些事件写入队列的Rails3应用。现在我想在服务器上创建一个服务，每x秒轮询一次队列，并按计划执行其他任务。除了创建ruby​​脚本并通过cron作业运行它之外，还有其他稳定的替代方案吗？ 最佳答案 尽管启动基于Rails的持久任务是一种选择，但您可能希望查看更有序的系统，例如delayed_job或Starling管理您的工作量。我建议不要在cron中运行某些东西，因为启动整个Rails堆栈的开销可能很大。每隔几秒运行一次它是不切实际的，因为Rails上的启动时间通常为5-15秒，具体取决于您的硬件。不过，每天这样做几

  10. 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

随机推荐