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

【Leetcode合集】20. 有效的括号

20. 有效的括号

20. 有效的括号

代码仓库地址: https://github.com/slience-me/Leetcode

个人博客 :https://slienceme.xyz

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

有效字符串需满足:

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

示例 1:

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

示例 2:

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

示例 3:

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

提示:

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

方案1:暴力解

第一种纯暴力解

class Solution {
public:bool isValid1(string s) {stack<char> st_char;for (const auto &item: s){if (item=='(' || item=='[' || item=='{'){st_char.push(item);} else {if(!st_char.empty()){char temp = st_char.top();st_char.pop();if (!item) {return false;} else if (item==')' && temp!='('){return false;} else if(item==']' && temp!='['){return false;}else if(item=='}' && temp!='{'){return false;}} else {return false;}}}if (st_char.empty()){return true;} else {return false;}}
};

执行用时分布 4ms 击败35.12%使用 C++ 的用户

消耗内存分布6.47MB 击败57.33%使用 C++ 的用户

方案2:初次优化

优化代码结构

class Solution {
public:bool isValid(string s) {stack<char> parentheses;unordered_map<char, char> mapping = {{')', '('}, {']', '['}, {'}', '{'}};for (char c : s) {if (c == '(' || c == '[' || c == '{') {parentheses.push(c);} else {// 栈为空或者栈顶与当前括号不对应if (parentheses.empty() || parentheses.top() != mapping[c]) {return false;}parentheses.pop();}}return parentheses.empty();}
};

执行用时分布 4ms 击败35.12%使用 C++ 的用户

消耗内存分布6.57MB 击败19.98%使用 C++ 的用户

方案3:再优化

特殊情况立即截断

class Solution {
public:bool isValid(string s) {// 奇数直接截断if (s.length() % 2 == 1) {return false;}stack<char> parentheses;unordered_map<char, char> mapping = {{')', '('},{']', '['},{'}', '{'}};int leftSum = 0;for (char c: s) {// 左括号数量>总括号的一半 立即截断if (leftSum>(s.length()/2)){return false;}if (c == '(' || c == '[' || c == '{') {parentheses.push(c);leftSum++;} else {// 栈为空或者栈顶与当前括号不对应if (parentheses.empty() || parentheses.top() != mapping[c]) {return false;}parentheses.pop();}}return parentheses.empty();}
};

执行用时分布 0ms 击败100%使用 C++ 的用户

消耗内存分布6.72MB 击败7.68%使用 C++ 的用户

相关文章:

【Leetcode合集】20. 有效的括号

20. 有效的括号 20. 有效的括号 代码仓库地址&#xff1a; https://github.com/slience-me/Leetcode 个人博客 &#xff1a;https://slienceme.xyz 给定一个只包括 (&#xff0c;)&#xff0c;{&#xff0c;}&#xff0c;[&#xff0c;] 的字符串 s &#xff0c;判断字符串…...

OpenGL 绘制线(Qt)

文章目录 一、简介二、实现代码三、实现效果参考资料一、简介 这里同样对OpenGL中的绘制线操作进行封装,便于后续的操作,很多形状也都是基于线来生成的,如圆形等。 二、实现代码 LineDrawable.h #ifndef LINE_DRAWABLE_H #define LINE_DRAWABLE_H#include...

Java | 多线程并发编程CountDownLatch实践

关注&#xff1a;CodingTechWork 引言 在一次数据割接需求中&#xff0c;数据需要通过编程的方式进行转移割接到新平台&#xff0c;此时若串行化方式&#xff0c;无疑会拉锯此次战斗&#xff0c;所以首当其冲要使用并发编程来降低割接时长。  本次主要考虑使用CountDownLatc…...

分布式定时任务系列6:XXL-job触发日志过大引发的CPU告警

传送门 分布式定时任务系列1&#xff1a;XXL-job安装 分布式定时任务系列2&#xff1a;XXL-job使用 分布式定时任务系列3&#xff1a;任务执行引擎设计 分布式定时任务系列4&#xff1a;任务执行引擎设计续 分布式定时任务系列5&#xff1a;XXL-job中blockingQueue的应用 …...

Spark RDD、DataFrame和Dataset的区别和联系

一、三种数据介绍 是Spark中的三种不同的数据结构&#xff0c;它们都可以用于分布式数据处理&#xff0c;但是它们的实现方式和使用方法略有不同。 RDD&#xff08;弹性分布式数据集&#xff09; RDD是Spark最初的核心数据结构&#xff0c;它是一个分布式的、只读的、可容错的…...

代码随想录算法训练营第四十五天|139.单词拆分、背包问题总结

LeetCode 139. 单词拆分 题目链接&#xff1a;139. 单词拆分 - 力扣&#xff08;LeetCode&#xff09; 这道题使用完全背包来实现&#xff0c;我们首先考虑字符串是否可以由字符串列表组成&#xff0c;因此dp数组大小为n 1 &#xff0c;其意义是&#xff0c;在n个位置时是否能…...

深度学习卫星遥感图像检测与识别 -opencv python 目标检测 计算机竞赛

文章目录 0 前言1 课题背景2 实现效果3 Yolov5算法4 数据处理和训练5 最后 0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; **深度学习卫星遥感图像检测与识别 ** 该项目较为新颖&#xff0c;适合作为竞赛课题方向&#xff0c;学长非常推荐…...

wxWidgets 3.2.4发布 —— 发布于2023年11月11日

稳定的3.2系列中的另一个版本现在可以在GitHub上获得。您可以在那里找到包含库源代码和文档的归档文件&#xff0c;以及所选Windows编译器&#xff08;如Microsoft Visual C、MinGW-w64和TDM-GCC&#xff09;的二进制文件。您还可以阅读此版本的更新文档&#xff0c;特别是&…...

PyQt6运行QTDesigner生成的ui文件程序

2024版 PyQt6 Python桌面开发 视频教程(无废话版) 玩命更新中~_哔哩哔哩_bilibili2024版 PyQt6 Python桌面开发 视频教程(无废话版) 玩命更新中~共计18条视频&#xff0c;包括&#xff1a;2024版 PyQt6 Python桌面开发 视频教程(无废话版) 玩命更新中~、第2讲 PyQt6库和工具库Q…...

基于mediapipe的人手21点姿态检测模型—CPU上检测速度惊人

前期的文章,我们介绍了MediaPipe对象检测与对象分类任务,也分享了MediaPipe的人手手势识别。在进行人手手势识别前,MediaPipe首先需要进行人手的检测与人手坐标点的检测,经过以上的检测后,才能把人手的坐标点与手势结合起来,进行相关的手势识别。 MediaPipe人手坐标点检测…...

系统架构设计: 21 论敏捷软件开发方法及其应用

论敏捷软件开发方法及其应用 请围绕“敏捷软件开发方法及其应用”论题,依次从以下三个方面进行论述。 ①简述你所参与开发的运用了敏捷技术的项目,以及你所担任的工作; ②分析并讨论敏捷<...

【深度学习】脸部修复,CodeFormer,论文,实战

代码&#xff1a; https://github.com/sczhou/CodeFormer https://huggingface.co/spaces/sczhou/CodeFormer 论文&#xff1a;https://arxiv.org/abs/2206.11253 Towards Robust Blind Face Restoration with Codebook Lookup Transformer 文章目录 论文摘要1 引言2 相关工…...

OpenGL_Learn14(光照贴图)

1. 漫反射贴图 在光照场景中&#xff0c;它通常叫做一个漫反射贴图(Diffuse Map)&#xff08;3D艺术家通常都这么叫它&#xff09;&#xff0c;它是一个表现了物体所有的漫反射颜色的纹理图像。 我们会将纹理储存为Material结构体中的一个sampler2D 。我们将之前定义的vec3漫反…...

【JVM精讲与GC调优教程(概述)】

如何理解虚拟机(JVM)跨语言的平台 java虚拟机根本不关心运行在其内部的程序到底是使用何种编程语言编写的,他只关心“字节码”文件。 java不是最强大的语言,但是JVN是最强大的虚拟机。 不存在内存溢出? 内存泄露? JAVA = (C++)–; 垃圾回收机制为我们打理了很多繁琐的…...

蓝桥杯物联网竞赛_STM32L071_2_继电器控制

Stm32l071原理图&#xff1a; PA11与PA12连接着UNL2803 ULN2803是一种集成电路芯片&#xff0c;通常被用作高电压和高电流负载的驱动器。 ULN2803是一个达林顿阵列&#xff0c;当输入引脚&#xff08;IN1至IN8&#xff09;被连接到正电源时&#xff0c;相应的输出引脚&#xff…...

python之pyqt专栏2-项目文件解析

项目结构 在上一篇文章python之pyqt专栏1-环境搭建&#xff0c;创建新的pyqt项目&#xff0c;下面我们来看一下这个项目下的文件。 从下面的文件结构图可以看到&#xff0c;该项目下有3个文件&#xff0c;untitled.ui,untitled.py 以及main.py。 QtDesigner可以UI界面的方式&am…...

Kafka 集群如何实现数据同步

Kafka 介绍 Kafka 是一个高吞吐的分布式消息系统&#xff0c;不但像传统消息队列&#xff08;RaabitMQ、RocketMQ等&#xff09;那样能够【异步处理、流量消峰、服务解耦】 还能够把消息持久化到磁盘上&#xff0c;用于批量消费。除此之外由于 Kafka 被设计成分布式系统&…...

opencv- CLAHE 有限对比适应性直方图均衡化

CLAHE&#xff08;Contrast Limited Adaptive Histogram Equalization&#xff09;是一种对比度有限的自适应直方图均衡化技术&#xff0c;它能够提高图像的对比度而又避免过度增强噪声。 在OpenCV中&#xff0c;cv2.createCLAHE() 函数用于创建CLAHE对象&#xff0c;然后可以…...

IOS免签封装打包苹果APP的方法

IOS免签app封装打包苹果APP的方法如下&#xff1a; 准备一个未签名的IPA文件。获取一个企业证书或个人证书&#xff0c;用于签名IPA文件。将证书添加到Keychain Access中。安装iOS App Signer&#xff08;可以在网上找到相关下载链接&#xff09;。打开iOS App Signer&#xf…...

Springboot引入分布式搜索引擎Es RestAPI

文章目录 RestAPI初始化RestClient创建索引库删除索引库判断索引库是否存在总结 RestClient操作文档增加文档数据查询文档删除文档修改文档批量导入文档小结 RestAPI ES官方提供了各种不同语言的客户端&#xff0c;用来操作ES。这些客户端的本质就是组装DSL语句&#xff0c;通…...

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

如何将联系人从 iPhone 转移到 Android

从 iPhone 换到 Android 手机时&#xff0c;你可能需要保留重要的数据&#xff0c;例如通讯录。好在&#xff0c;将通讯录从 iPhone 转移到 Android 手机非常简单&#xff0c;你可以从本文中学习 6 种可靠的方法&#xff0c;确保随时保持连接&#xff0c;不错过任何信息。 第 1…...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来&#xff0c;实在找不到&#xff0c;希望有大佬教一下我。 还有就会议时间&#xff0c;我感觉不是图片时间&#xff0c;因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

Java多线程实现之Thread类深度解析

Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...

在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)

考察一般的三次多项式&#xff0c;以r为参数&#xff1a; p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]&#xff1b; 此多项式的根为&#xff1a; 尽管看起来这个多项式是特殊的&#xff0c;其实一般的三次多项式都是可以通过线性变换化为这个形式…...

mac 安装homebrew (nvm 及git)

mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用&#xff1a; 方法一&#xff1a;使用 Homebrew 安装 Git&#xff08;推荐&#xff09; 步骤如下&#xff1a;打开终端&#xff08;Terminal.app&#xff09; 1.安装 Homebrew…...

uniapp 实现腾讯云IM群文件上传下载功能

UniApp 集成腾讯云IM实现群文件上传下载功能全攻略 一、功能背景与技术选型 在团队协作场景中&#xff0c;群文件共享是核心需求之一。本文将介绍如何基于腾讯云IMCOS&#xff0c;在uniapp中实现&#xff1a; 群内文件上传/下载文件元数据管理下载进度追踪跨平台文件预览 二…...