【Leetcode合集】20. 有效的括号
20. 有效的括号
20. 有效的括号
代码仓库地址: https://github.com/slience-me/Leetcode
个人博客 :https://slienceme.xyz
给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1:
输入:s = "()"
输出:true
示例 2:
输入:s = "()[]{}"
输出:true
示例 3:
输入:s = "(]"
输出:false
提示:
1 <= s.length <= 104s仅由括号'()[]{}'组成
方案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. 有效的括号 代码仓库地址: https://github.com/slience-me/Leetcode 个人博客 :https://slienceme.xyz 给定一个只包括 (,),{,},[,] 的字符串 s ,判断字符串…...
OpenGL 绘制线(Qt)
文章目录 一、简介二、实现代码三、实现效果参考资料一、简介 这里同样对OpenGL中的绘制线操作进行封装,便于后续的操作,很多形状也都是基于线来生成的,如圆形等。 二、实现代码 LineDrawable.h #ifndef LINE_DRAWABLE_H #define LINE_DRAWABLE_H#include...
Java | 多线程并发编程CountDownLatch实践
关注:CodingTechWork 引言 在一次数据割接需求中,数据需要通过编程的方式进行转移割接到新平台,此时若串行化方式,无疑会拉锯此次战斗,所以首当其冲要使用并发编程来降低割接时长。 本次主要考虑使用CountDownLatc…...
分布式定时任务系列6:XXL-job触发日志过大引发的CPU告警
传送门 分布式定时任务系列1:XXL-job安装 分布式定时任务系列2:XXL-job使用 分布式定时任务系列3:任务执行引擎设计 分布式定时任务系列4:任务执行引擎设计续 分布式定时任务系列5:XXL-job中blockingQueue的应用 …...
Spark RDD、DataFrame和Dataset的区别和联系
一、三种数据介绍 是Spark中的三种不同的数据结构,它们都可以用于分布式数据处理,但是它们的实现方式和使用方法略有不同。 RDD(弹性分布式数据集) RDD是Spark最初的核心数据结构,它是一个分布式的、只读的、可容错的…...
代码随想录算法训练营第四十五天|139.单词拆分、背包问题总结
LeetCode 139. 单词拆分 题目链接:139. 单词拆分 - 力扣(LeetCode) 这道题使用完全背包来实现,我们首先考虑字符串是否可以由字符串列表组成,因此dp数组大小为n 1 ,其意义是,在n个位置时是否能…...
深度学习卫星遥感图像检测与识别 -opencv python 目标检测 计算机竞赛
文章目录 0 前言1 课题背景2 实现效果3 Yolov5算法4 数据处理和训练5 最后 0 前言 🔥 优质竞赛项目系列,今天要分享的是 🚩 **深度学习卫星遥感图像检测与识别 ** 该项目较为新颖,适合作为竞赛课题方向,学长非常推荐…...
wxWidgets 3.2.4发布 —— 发布于2023年11月11日
稳定的3.2系列中的另一个版本现在可以在GitHub上获得。您可以在那里找到包含库源代码和文档的归档文件,以及所选Windows编译器(如Microsoft Visual C、MinGW-w64和TDM-GCC)的二进制文件。您还可以阅读此版本的更新文档,特别是&…...
PyQt6运行QTDesigner生成的ui文件程序
2024版 PyQt6 Python桌面开发 视频教程(无废话版) 玩命更新中~_哔哩哔哩_bilibili2024版 PyQt6 Python桌面开发 视频教程(无废话版) 玩命更新中~共计18条视频,包括:2024版 PyQt6 Python桌面开发 视频教程(无废话版) 玩命更新中~、第2讲 PyQt6库和工具库Q…...
基于mediapipe的人手21点姿态检测模型—CPU上检测速度惊人
前期的文章,我们介绍了MediaPipe对象检测与对象分类任务,也分享了MediaPipe的人手手势识别。在进行人手手势识别前,MediaPipe首先需要进行人手的检测与人手坐标点的检测,经过以上的检测后,才能把人手的坐标点与手势结合起来,进行相关的手势识别。 MediaPipe人手坐标点检测…...
系统架构设计: 21 论敏捷软件开发方法及其应用
论敏捷软件开发方法及其应用 请围绕“敏捷软件开发方法及其应用”论题,依次从以下三个方面进行论述。 ①简述你所参与开发的运用了敏捷技术的项目,以及你所担任的工作; ②分析并讨论敏捷<...
【深度学习】脸部修复,CodeFormer,论文,实战
代码: https://github.com/sczhou/CodeFormer https://huggingface.co/spaces/sczhou/CodeFormer 论文:https://arxiv.org/abs/2206.11253 Towards Robust Blind Face Restoration with Codebook Lookup Transformer 文章目录 论文摘要1 引言2 相关工…...
OpenGL_Learn14(光照贴图)
1. 漫反射贴图 在光照场景中,它通常叫做一个漫反射贴图(Diffuse Map)(3D艺术家通常都这么叫它),它是一个表现了物体所有的漫反射颜色的纹理图像。 我们会将纹理储存为Material结构体中的一个sampler2D 。我们将之前定义的vec3漫反…...
【JVM精讲与GC调优教程(概述)】
如何理解虚拟机(JVM)跨语言的平台 java虚拟机根本不关心运行在其内部的程序到底是使用何种编程语言编写的,他只关心“字节码”文件。 java不是最强大的语言,但是JVN是最强大的虚拟机。 不存在内存溢出? 内存泄露? JAVA = (C++)–; 垃圾回收机制为我们打理了很多繁琐的…...
蓝桥杯物联网竞赛_STM32L071_2_继电器控制
Stm32l071原理图: PA11与PA12连接着UNL2803 ULN2803是一种集成电路芯片,通常被用作高电压和高电流负载的驱动器。 ULN2803是一个达林顿阵列,当输入引脚(IN1至IN8)被连接到正电源时,相应的输出引脚ÿ…...
python之pyqt专栏2-项目文件解析
项目结构 在上一篇文章python之pyqt专栏1-环境搭建,创建新的pyqt项目,下面我们来看一下这个项目下的文件。 从下面的文件结构图可以看到,该项目下有3个文件,untitled.ui,untitled.py 以及main.py。 QtDesigner可以UI界面的方式&am…...
Kafka 集群如何实现数据同步
Kafka 介绍 Kafka 是一个高吞吐的分布式消息系统,不但像传统消息队列(RaabitMQ、RocketMQ等)那样能够【异步处理、流量消峰、服务解耦】 还能够把消息持久化到磁盘上,用于批量消费。除此之外由于 Kafka 被设计成分布式系统&…...
opencv- CLAHE 有限对比适应性直方图均衡化
CLAHE(Contrast Limited Adaptive Histogram Equalization)是一种对比度有限的自适应直方图均衡化技术,它能够提高图像的对比度而又避免过度增强噪声。 在OpenCV中,cv2.createCLAHE() 函数用于创建CLAHE对象,然后可以…...
IOS免签封装打包苹果APP的方法
IOS免签app封装打包苹果APP的方法如下: 准备一个未签名的IPA文件。获取一个企业证书或个人证书,用于签名IPA文件。将证书添加到Keychain Access中。安装iOS App Signer(可以在网上找到相关下载链接)。打开iOS App Signer…...
Springboot引入分布式搜索引擎Es RestAPI
文章目录 RestAPI初始化RestClient创建索引库删除索引库判断索引库是否存在总结 RestClient操作文档增加文档数据查询文档删除文档修改文档批量导入文档小结 RestAPI ES官方提供了各种不同语言的客户端,用来操作ES。这些客户端的本质就是组装DSL语句,通…...
XML Group端口详解
在XML数据映射过程中,经常需要对数据进行分组聚合操作。例如,当处理包含多个物料明细的XML文件时,可能需要将相同物料号的明细归为一组,或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码,增加了开…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...
2021-03-15 iview一些问题
1.iview 在使用tree组件时,发现没有set类的方法,只有get,那么要改变tree值,只能遍历treeData,递归修改treeData的checked,发现无法更改,原因在于check模式下,子元素的勾选状态跟父节…...
Axios请求超时重发机制
Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式: 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...
Spring AI与Spring Modulith核心技术解析
Spring AI核心架构解析 Spring AI(https://spring.io/projects/spring-ai)作为Spring生态中的AI集成框架,其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似,但特别为多语…...
Pinocchio 库详解及其在足式机器人上的应用
Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库,专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性,并提供了一个通用的框架&…...
GitHub 趋势日报 (2025年06月06日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...
git: early EOF
macOS报错: Initialized empty Git repository in /usr/local/Homebrew/Library/Taps/homebrew/homebrew-core/.git/ remote: Enumerating objects: 2691797, done. remote: Counting objects: 100% (1760/1760), done. remote: Compressing objects: 100% (636/636…...
CMS内容管理系统的设计与实现:多站点模式的实现
在一套内容管理系统中,其实有很多站点,比如企业门户网站,产品手册,知识帮助手册等,因此会需要多个站点,甚至PC、mobile、ipad各有一个站点。 每个站点关联的有站点所在目录及所属的域名。 一、站点表设计…...
ffmpeg(三):处理原始数据命令
FFmpeg 可以直接处理原始音频和视频数据(Raw PCM、YUV 等),常见场景包括: 将原始 YUV 图像编码为 H.264 视频将 PCM 音频编码为 AAC 或 MP3对原始音视频数据进行封装(如封装为 MP4、TS) 处理原始 YUV 视频…...
