力扣20、有效的括号(简单)

1 题目描述

图1 题目描述

2 题目解读

        给定的字符串只包含括号,判断这个字符串中的括号是否按照正确顺序出现,即这个字符串是否有效。

3 解法一:栈

        C++的STL中的stack,在解题时非常好用。

3.1 解题思路

        使用栈stk,并枚举字符串s的每一个字符。如果字符c是右括号,就进行以下判断,否则将其压入stk栈中:如果栈stk非空,且栈顶字符是对应的左括号,则弹出stk栈顶元素,否则返回false。

3.2 设计代码

class Solution {
public:
    bool isValid(string s) {
        int n = s.size();
        if (n % 2 == 1) {
            return false;
        }

        unordered_map<char, char> pairs = {
            {')', '('},
            {']', '['},
            {'}', '{'}
        };
        stack<char> stk;
        for (char ch : s) {
            if (pairs.count(ch)) {
                if (stk.empty() || stk.top() != pairs[ch]) {
                    return false;
                }
                stk.pop();
            }
            else {
                stk.push(ch);
            }
        }
        return stk.empty();
    }
};

3.3 复杂度分析

  • 时间复杂度:O(n)。其中,n是字符串s的长度。
  • 空间复杂度:O(n+\left | \sum \right |)。其中,\sum表示字符集,本题中字符串只包含6种括号,\left | \sum \right |=6。代码中使用了栈和哈希表,空间复杂度分别为O(n)O(\left | \sum \right |),将这两个空间复杂度相加,则得到总空间复杂度。

3.4 提交结果

图2 提交结果

4 解题心得

  • C++的STL中,栈stack在解题时非常好用。
  • 哈希表在使用时,有空间复杂度。
  • 哈希表的count()方法,可以在哈希表中查找元素。

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

使用 Ant Design Pro 初始化前端项目

一、使用 pro-cli 来快速的初始化脚手架 1. 打开终端&#xff0c;输入命令 # 使用 npm npm i ant-design/pro-cli -g # create 后面加要初始化的项目名称 pro create leapi-frontend 2. 报错 PS D:\code> pro create leapi-frontend pro : 无法加载文件 D:\tools\nodejs…

Java基础—面向对象OOP—18三大特性:封装、继承与多态

由于本身理解还不是很到位&#xff0c;所以写的很绕&#xff0c;后续待补充优化 1、封装&#xff08;底层&#xff09;&#xff1a;该露的露&#xff0c;该藏的藏 高内聚&#xff1a;类的内部数据操作细节自己完成&#xff0c;不允许外部干涉低耦合&#xff1a;仅暴露少量的方…

计算机二级C语言的注意事项及相应真题-6-程序填空

目录 51.将参数num按升序插入到数组xx中52.在数组中找出两科成绩之和最高的学生并返回其在数组中的下标53.删除所有串长超过k的字符串&#xff0c;输出剩下的字符串54.根据所给的一组学生的成绩&#xff0c;计算出平均成绩&#xff0c;并计算低于平均成绩的学生的平均成绩55.将…

Python算法题集_找到字符串中所有字母异位词

本文为Python算法题集之一的代码示例 题目438&#xff1a;找到字符串中所有字母异位词 说明&#xff1a;给定两个字符串 s 和 p&#xff0c;找到 s 中所有 p 的 异位词 的子串&#xff0c;返回这些子串的起始索引。不考虑答案输出的顺序。 异位词 指由相同字母重排列形成的字…

【c++】高精度算法(洛谷刷题2024)玩具谜题详解(含图解)

系列文章目录 第三题&#xff1a;玩具谜题 视频讲解&#xff1a;http://【洛谷题单 - 算法 - 高精度】https://www.bilibili.com/video/BV1Ym4y1s7BD?vd_source66a11ab493493f42b08b31246a932bbb 文章目录 目录 系列文章目录 文章目录 前言 一、题目分析以及思考 二、代码…

查询redis路径,清除redis缓存

查询redis路径 1、执行ps -ef | grep redis 命令&#xff0c;结果如下&#xff08;记住PID&#xff09; 2、执行ps -u 系统用户名&#xff0c;进一步确定进程id, 我这里的系统用户名是root&#xff0c;执行ps -u root&#xff0c;结果如下&#xff1a; 结合1的操作结果图可知…

SERVLET生命周期API

SERVLET生命周期API 在servlet的生命周期中,将发生创建Servlet上下文、创建会话、向Servlet上下文添加属性等各种事件。在servlet的生命周期内发生事件时,Web容器将通知侦听器类。要接收事件的通知,侦听器类需要扩展Servlet API的侦听器接口。 1. 事件类型 servlet生命周期…

关于如何利用ChatGPT提高编程效率的

自从去年ChatGPT3.5推出以后&#xff0c;这一年时间在编程过程中我也在慢慢熟悉人工智能的使用&#xff0c;目前来看即使是免费的ChatGPT3.5对于编程效率的提升也是有很大帮助的&#xff0c;虽然在使用过程中确实出现了一些问题&#xff0c;本文记录下我的一些心得体会和用法。…

Peter算法小课堂—二叉堆(优先队列)

课前小视频&#xff1a;(7 封私信 / 62 条消息) 看动画&#xff0c;学算法&#xff0c;C实现建立二叉堆&#xff0c;优先队列和堆排序的基础 - 知乎 (zhihu.com) 二叉堆&#xff08;优先队列&#xff09; 大家想想&#xff0c;什么数据结构能做到插入&#xff08;删除&#x…

IDEA 构建开发环境

本博客主要讲解了如何创建一个Maven构建Java项目。&#xff08;本文是创建一个用Maven构建项目的方式&#xff0c;所以需要对Maven有一定的了解&#xff09; IDEA 构建开发环境 一、创建一个空工程二、构建一个普通的Maven模块 一、创建一个空工程 创建一个空的工程 * 设置整…

声音模拟训练

环境配置 参考文章&#xff1a; https://github.com/SUC-DriverOld/so-vits-svc-Chinese-Detaild-Documents 1:打开CMD nvidia-smi.exe 查询显卡 cuda VERSION:12.3 2:打开https://pytorch.org/get-started 我的系统是12.3 3&#xff1a;使用google 搜索 nvidia develope…

哈希概念 | 哈希函数 | 哈希冲突 | 哈希桶实现 | 哈希线性探测代码实现 | 闭散列 | 开散列 | 字符串哈希算法

文章目录 1.哈希概念2.哈希冲突3.解决哈希冲突3.1.闭散列3.2.开散列 4.字符串哈希算法 1.哈希概念 顺序结构以及平衡树中&#xff0c;元素关键码与其存储位置之间没有对应的关系&#xff0c;因此在查找一个元素时&#xff0c;必须要经过关键码的多次比较。如果一个顺序结构&am…

80.网游逆向分析与插件开发-背包的获取-自动化助手显示物品数据1

内容参考于&#xff1a;易道云信息技术研究院VIP课 上一个内容&#xff1a;升级Notice类获得背包基址-CSDN博客 码云地址&#xff08;ui显示角色数据 分支&#xff09;&#xff1a;https://gitee.com/dye_your_fingers/sro_-ex.git 码云版本号&#xff1a;3be017de38c50653b…

BGP:04 fake-as

使用 fake-as 可以将本地真实的 AS 编号隐藏&#xff0c;其他 AS 内的对等体在指定本端对等体所在的AS 编号时&#xff0c;应该设置成这个伪AS 编号。 这是实验拓扑&#xff0c;IBGP EBGP 邻居都使用物理接口来建立 基本配置&#xff1a; R1: sys sysname R1 int loo0 ip add…

面了快手电商数据分析师岗(实习),被问的汗流浃背。。。。

最近技术群的一位同学&#xff0c;分享了他面试快手数据分析师岗(实习)的经验。我看了一下面试题&#xff0c;说实话内容不难&#xff0c;他直言没有认真准备。 今天整理后分享给大家&#xff0c;如果你对这块面试感兴趣&#xff0c;可以文末加入我们的面试、技术群 内容 1&…

时序预测 | Python基于Multihead-Attention-TCN-LSTM的时间序列预测

目录 效果一览基本介绍程序设计参考资料 效果一览 基本介绍 时序预测 | Python基于Multihead-Attention-TCN-LSTM的时间序列预测 Multihead-Attention-TCN-LSTM&#xff08;多头注意力-TCN-LSTM&#xff09;是一种结合了多个注意力机制、时序卷积网络&#xff08;TCN&#xff0…

解决方案|构建生物医学科技桥梁:镭速客户案例分享

随着生物科技在医学领域的快速发展&#xff0c;数据传输在实现医疗创新和科学研究中的重要性变得日益突出。数据不仅庞大&#xff0c;而且高度敏感&#xff0c;传统的数据传输方式已经无法满足医学行业对高效、快速的数据交流需求。 如今市场上备受关注的解决方案是基于UDP传输…

计算机毕业设计 基于SpringBoot的校园闲置物品交易系统的设计与实现 Java实战项目 附源码+文档+视频讲解

博主介绍&#xff1a;✌从事软件开发10年之余&#xff0c;专注于Java技术领域、Python人工智能及数据挖掘、小程序项目开发和Android项目开发等。CSDN、掘金、华为云、InfoQ、阿里云等平台优质作者✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精…

【gmsh源码阅读】OCC对象绑定tag及获取几何与网格映射关系

一、Tag是什么&#xff1f; gmsh中的几何模型相对于OCC的模型增加了id编号&#xff0c;也叫tag&#xff0c;在gmsh中可以显示出来。在gmsh中&#xff0c;点、线、面、体都有Tag&#xff0c;以方便对其查找定位查找。在OCC中TopoDS_Shape只有几何与拓扑结构&#xff0c;没有唯一…

数据中心代理IP:最优性价比业务应用指南

数据中心代理IP在应对高速高并发的业务时&#xff0c;以独特的高速传输&#xff0c;游刃有余地应对多任务处理&#xff0c;适合于特定业务场景的高效加速。理性选用数据中心代理IP&#xff0c;可以为业务将迎来更加稳健和迅速的发展。今天&#xff0c;我们将揭示数据中心代理IP…