LeetCode算法栈—有效的括号

目录

有效的括号

用到的数据结构:

位运算、Map 和 Stack

Stack 常用的函数:

题解:

代码:

运行结果;


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

有效字符串需满足:

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

示例 1:

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

示例 2:

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

示例 3:

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

提示:

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

用到的数据结构:

位运算、Map 和 Stack
  1. 使用位运算 (n&1)==1 来判断字符串长度 n 是否为奇数,如果是奇数则直接返回 false。因为有效的括号序列必须是成对出现的。

  2. 使用 Map 数据结构 buckets 来存储左右括号的映射关系。键值对的形式为左括号-右括号。

  3. 使用了 Stack 栈数据结构 stack 来存储遍历过程中的左括号

Stack 常用的函数:
  • push(E item): 将元素 item 压入栈顶。

  • pop(): 弹出并返回栈顶的元素。

  • peek(): 返回栈顶的元素,但不进行弹出操作。

  • isEmpty(): 判断栈是否为空,如果为空则返回 true,否则返回 false。

  • size(): 返回栈中元素的个数。

题解:

  1. 遍历字符串的每个字符,如果当前字符是左括号,则将其入栈;如果当前字符是右括号,则判断栈是否为空或者当前右括号是否与栈顶的左括号匹配。如果不匹配,则返回 false;如果匹配,则弹出栈顶的左括号。

  2. 最后判断栈是否为空,如果为空则表示所有的左括号都有相应的右括号匹配,返回 true;否则返回 false。

代码:

class Solution {public boolean isValid(String s) {int n=s.length();// 判断奇偶if((n&1)==1) return false;// 存储左右括号映射Map<Character,Character> buckets=new HashMap<>();buckets.put('(',')');buckets.put('[',']');buckets.put('{','}');// 存储左括号Stack<Character> stack =new Stack<>();// 存储当前括号字符char bucket;// 遍历处理for(int i=0;i<n;i++){bucket=s.charAt(i);if(buckets.containsKey(bucket)){stack.push(bucket);// 为左括号,入栈}else if(stack.isEmpty() || bucket !=buckets.get(stack.peek())){return false;//当前为右括号但是此时栈为空或和栈顶不匹配}else{stack.pop();//当前右括号和栈顶匹配,弹出栈顶}}return stack.isEmpty();}
}

运行结果;

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/163614.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

模拟IIC通讯协议(stm32)(硬件iic后面在补)

一、IIC基础知识总结。 1、IIC通讯需要两条线就可以&#xff0c;SCL、SDA。 2、IIC的数据传输的速率&#xff0c;不同的ic是不同的&#xff0c;根据电平维持的延时函数的时间来确定IIC数据传输的速率. 3、IIC的延时函数可以使用延时函数&#xff0c;延时函数一般使用系统滴答时…

20款VS Code实用插件推荐

前言&#xff1a; VS Code是一个轻量级但功能强大的源代码编辑器&#xff0c;轻量级指的是下载下来的VS Code其实就是一个简单的编辑器&#xff0c;强大指的是支持多种语言的环境插件拓展&#xff0c;也正是因为这种支持插件式安装环境开发让VS Code成为了开发语言工具中的霸主…

Fast DDS之Subscriber

目录 SubscriberSubscriberQosSubscriberListener创建Subscriber DataReaderSampleInfo读取数据 Subscriber扮演容器的角色&#xff0c;里面可以有很多DataReaders&#xff0c;它们使用Subscriber的同一份SubscriberQos配置。Subscriber可以承载不同Topic和数据类型的DataReade…

【QT】QTreeWidget

新建项目 第一步&#xff1a;设置头标签 第二步&#xff1a;设置item 第三步&#xff1a;创建子item&#xff0c;挂载在顶层item下 完整代码 #include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::W…

C++项目——云备份-①-项目介绍环境搭建

文章目录 专栏导读1.什么是云备份2.实现目标3.服务端程序负责功能4.服务端功能模块划分5.客户端程序负责功能6.客户端功能模块划分开发环境环境搭建1. gcc 升级7.3版本2.安装 jsoncpp 库3.下载bundle数据压缩库4.下载 httplib 库 专栏导读 &#x1f338;作者简介&#xff1a;花…

babel6使用ES2020最新js语法

babel6使用ES2020最新js语法 Babel 6 原本是不支持 ES2020 语法&#xff0c;因为它是在 Babel 7 中引入的。如果您想使用 ES2020 语法&#xff0c;您需要将 Babel 6 升级到 Babel 7 或更高版本(推荐),当然也可以在bebel6中安装支持某个语法的plugin,比如你想使用 ES2020 中的可…

Linux程序调试器——gdb的使用

gdb的概述 GDB 全称“GNU symbolic debugger”&#xff0c;从名称上不难看出&#xff0c;它诞生于 GNU 计划&#xff08;同时诞生的还有 GCC、Emacs 等&#xff09;&#xff0c;是 Linux 下常用的程序调试器。发展至今&#xff0c;GDB 已经迭代了诸多个版本&#xff0c;当下的…

完美解决 在将最终稿件上传到 IEEE PDF eXpress进行格式检查是出现“font not embedded“的问题 (不会出现自动压缩图像的现象)

最近中了一篇IEEE的论文&#xff0c;在校稿阶段&#xff0c;final paper是需要通过IEEE PDF eXpress网站的格式检查&#xff0c;然后出现一下问题&#xff1a; Errors: Font TimesNewRomanPS-BoldMT, TimesNewRomanPS-ItalicMT, TimesNewRomanPSMT is not embedded 用人话说就…

模式植物GO背景基因集制作

一边学习&#xff0c;一边总结&#xff0c;一边分享&#xff01; 写在前面 关于GO背景基因集文件的制作&#xff0c;我们在很早以前也发过。近两天&#xff0c;自己在分析时候&#xff0c;也是被搞了头疼。想重新制作一份GO背景基因集&#xff0c;进行富集分析。但是结果&…

JAVAEE初阶相关内容第十五弹--网络編程

写在前 简单描述一下关于路由器的三层转发和交换机的二层转发。 路由器是三层转发-->在网络层转发。【需要解析出IP协议中的源IP、目的IP来规划路径】 交换机是二层转发-->在数据链路层转发。【只需要关注下一步发展到哪个相邻的设备上&#xff0c;不需要IP地址&#…

JAVA生成ORC格式文件

一、背景 由于需要用到用java生成hdfs文件并上传到指定目录中&#xff0c;在Hive中即可查询到数据&#xff0c;基于此背景&#xff0c;开发此工具类 ORC官方网站&#xff1a;https://orc.apache.org/ 二、支持数据类型 三、工具开发 package com.xx.util;import com.alibab…

【计算机网络笔记】分组交换中的报文交付时间计算例题

系列文章目录 什么是计算机网络&#xff1f; 什么是网络协议&#xff1f; 计算机网络的结构 数据交换之电路交换 数据交换之报文交换和分组交换 系列文章目录题目解答 题目 在下图所示的采用“存储-转发”方式的分组交换网络中所有链路的数据传输速率为100 Mbps&#xff0c;分…

node+vue+mysql后台管理系统

千千博客系统&#xff0c;该项目作为一套多功能的后台框架模板&#xff0c;适用于绝大部分的后台管理系统开发。基于 vue.js&#xff0c;使用 vue-cli3 脚手架&#xff0c;引用 Element UI 组件库&#xff0c;数据库直连mysql方便开发快速简洁好看的组件。 功能包含如下&#…

EtherNet/IP转Modbus TCP协议网关的接口

远创智控的YC-EIPM-TCP网关产品&#xff0c;它有什么作用呢&#xff1f;一起来了解一下吧&#xff01; 远创智控YC-EIPM-TCP网关产品可以通过各种数据接口和工业领域的仪表、PLC、计量设备等产品连接&#xff0c;实时采集这些设备中的运行数据、状态数据等信息&#xff0c;并把…

【javascript】内部引入与外部引入javascript

创建a.html 内部引入&#xff1a; 外部引入&#xff1a; 创建a.js 注意&#xff1a; 我这里的a.js和a.html是放在同一个目录下&#xff0c;如果a.js放在js的目录下&#xff0c;a.html 调用a.js的时候 <script src"/js/a.js"></script>

sqlmap --os-shell选项原理解析

文章目录 sqlmap --os-shell选项原理解析原理解析总结 sqlmap --os-shell选项原理解析 以sqli第一关为例。 --os-shell 是 SQLMap 工具的一个参数&#xff0c;用于在成功注入数据库后&#xff0c;执行操作系统命令并获取其输出。 sqlmap -u "http://192.168.188.199/sq…

【C++】特殊类的设计(只在堆、栈创建对象,单例对象)

&#x1f30f;博客主页&#xff1a; 主页 &#x1f516;系列专栏&#xff1a; C ❤️感谢大家点赞&#x1f44d;收藏⭐评论✍️ &#x1f60d;期待与大家一起进步&#xff01; 文章目录 一、请设计一个类&#xff0c;只能在堆上创建对象二、 请设计一个类&#xff0c;只能…

GO-unioffice实现word编辑

导包 import ("fmt""log""os""time""github.com/unidoc/unioffice/common/license""github.com/unidoc/unioffice/document" ) 创建word文件 func CreateFile(name string) {filename : name ".docx&quo…

【数据结构】栈

⭐ 作者&#xff1a;小胡_不糊涂 &#x1f331; 作者主页&#xff1a;小胡_不糊涂的个人主页 &#x1f4c0; 收录专栏&#xff1a;浅谈数据结构 &#x1f496; 持续更文&#xff0c;关注博主少走弯路&#xff0c;谢谢大家支持 &#x1f496; 栈-Stack 1. 什么是栈2. 栈的使用3.…

项目管理之分析项目特点的方法

在管理项目时&#xff0c;了解项目的目标和实现方法可以帮助我们更好地规划和执行项目。根据项目的目标和实现方法的不同&#xff0c;可以将项目分为四种类型&#xff1a;地、水、火和气。 对于工程项目&#xff0c;采用基于活动任务的计划管理方法&#xff0c;使用活动网络图…