当前位置: 首页 > article >正文

【Leetcode 热题 100】20. 有效的括号

问题背景

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

  • 左括号必须用相同类型的右括号闭合。
  • 左括号必须以正确的顺序闭合。
  • 每个右括号都有一个对应的相同类型的左括号。

数据约束

  • 1 ≤ s . l e n g t h ≤ 1 0 4 1 \le s.length \le 10 ^ 4 1s.length104
  • s s s 仅由括号 ‘()[]{}’ 组成

解题过程

经典括号匹配问题,可以用哈希表来映射左右括号辅助匹配,积累一下双大括号的匿名内部类初始化方式。
单纯写判断效率会更高,栈中要存储的是左括号对应的右括号。

具体实现

哈希映射

class Solution {
    public boolean isValid(String s) {
        if((s.length() & 1) != 0) {
            return false;
        }
        Map<Character, Character> map = new HashMap<>() {{
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};
        Stack<Character> stack = new Stack<>();
        for(char c : s.toCharArray()) {
            if(!map.containsKey(c)) {
                stack.push(c);
            } else if(stack.isEmpty() || stack.pop() != map.get(c)) {
                return false;
            }
        }
        return stack.isEmpty();
    }
}

直接判断

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

http://www.kler.cn/a/474312.html

相关文章:

  • 【杂谈】-50+个生成式人工智能面试问题(一)
  • 【漏洞工具】小米路由器任意文件读取漏洞python图形化框架利用工具(poc|exp)
  • QPS和TPS 的区别是什么?QPS 大了会有什么问题,怎么解决?
  • 数据库中锁与ETL的故障排除和性能优化
  • maven之插件调试
  • 联邦学习中的LoRA:FedLoRA
  • markdown语法中的表格快速转换成word中的表格。
  • 【网页自动化】篡改猴入门教程
  • C#标识符和关键字
  • 2025.01.15docker
  • Pytorch单、多GPU和CPU训练模型保存和加载
  • C++二十三种设计模式之观察者模式
  • 强化学习入门谈
  • Linux C/C++编程-UDP套接字编程示例
  • 微软人工智能研究院推出OLA-VLM:一种以视觉为中心的方法来优化多模态大型语言模型
  • Redis Stream
  • Git指令
  • 一文读懂单片机的串口
  • 基于R语言的DICE模型实践技术应用;评估气候变化对经济的影响以及不同减排政策的经济成本和效益
  • Dify进阶:使用FastAPI和Selenium构建远程浏览器控制与录屏服务
  • 蓝桥杯python省赛备战day2--数组枚举--845数组中的最长山脉-枚举算法刷题学习笔记3--leetcode
  • NoSQL 基础知识总结
  • python【数据结构】
  • RabbitMQ中的配置文件advanced.config
  • 配置嵌入式服务器
  • Vue3 监听属性