当前位置: 首页 > 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;通…...

强化学习核心算法与工程实践全解析

1. 强化学习基础概念解析强化学习&#xff08;Reinforcement Learning&#xff09;是机器学习领域中最接近人类学习方式的范式之一。与监督学习需要大量标注数据不同&#xff0c;强化学习通过"试错"机制让智能体&#xff08;Agent&#xff09;在与环境&#xff08;En…...

告别黑白终端:用C++转义序列为你的ROS_INFO和ROS_WARN消息添加高亮颜色(附完整代码示例)

告别黑白终端&#xff1a;用C转义序列为ROS日志注入视觉活力 在机器人操作系统&#xff08;ROS&#xff09;开发中&#xff0c;日志输出是我们与系统对话的重要窗口。想象一下&#xff0c;当你的机器人正在执行复杂任务时&#xff0c;终端里滚动着密密麻麻的黑白文字——重要错…...

从傅里叶级数到电路板:深入浅出理解方波里的奇次谐波(以30kHz信号为例)

从傅里叶级数到电路板&#xff1a;深入浅出理解方波里的奇次谐波&#xff08;以30kHz信号为例&#xff09; 当你在示波器上看到一个完美的方波时&#xff0c;是否想过它其实是由无数个正弦波"拼凑"而成的&#xff1f;这种看似简单的波形背后&#xff0c;隐藏着傅里叶…...

Phi-3.5-mini-instruct部署教程:WSL2环境下Windows本地运行vLLM+Chainlit全步骤

Phi-3.5-mini-instruct部署教程&#xff1a;WSL2环境下Windows本地运行vLLMChainlit全步骤 1. 环境准备与快速部署 在开始之前&#xff0c;请确保你的Windows系统已启用WSL2并安装了Ubuntu发行版。本教程将指导你完成从零开始的完整部署流程。 1.1 系统要求 Windows 10/11 …...

FPGA与ASIC设计优化:可移植性策略与实践

## 1. FPGA与ASIC设计优化概述现代数字系统设计中&#xff0c;FPGA和ASIC是两种关键实现方式。FPGA凭借其可重构特性&#xff0c;在原型验证和小批量产品中占据主导地位&#xff1b;而ASIC在大规模量产时展现出显著的性能和成本优势。本指南将深入探讨如何构建兼顾FPGA高效性和…...

Harepacker-resurrected终极指南:深度解析MapleStory游戏资源编辑全流程

Harepacker-resurrected终极指南&#xff1a;深度解析MapleStory游戏资源编辑全流程 【免费下载链接】Harepacker-resurrected All in one .wz file/map editor for MapleStory game files 项目地址: https://gitcode.com/gh_mirrors/ha/Harepacker-resurrected Harepac…...

基于ESP32的气象雷达站设计与实现

1. 项目概述这个基于ESP32的气象雷达站项目&#xff0c;是我最近完成的一个物联网气象监测解决方案。它通过7英寸触摸屏实时展示气象雷达图、云层覆盖、降雨强度和详细的多日预报数据。整套系统硬件成本控制在500元以内&#xff0c;却实现了接近专业气象站的功能体验。核心设计…...

从V模型到敏捷测试:HIL台架如何成为智能汽车软件快速迭代的‘加速器’

从V模型到敏捷测试&#xff1a;HIL台架如何成为智能汽车软件快速迭代的‘加速器’ 在智能汽车软件功能快速上线的背景下&#xff0c;传统的V模型开发流程正面临前所未有的挑战。当软件迭代周期从数月压缩到数周甚至数天时&#xff0c;如何确保每次变更都能得到充分验证&#xf…...

保姆级教程:用华为AC+AP搭建企业级Wi-Fi(旁挂三层+直接转发+漫游实战)

企业级Wi-Fi部署实战&#xff1a;华为ACAP旁挂三层组网与直接转发架构深度解析 当走进任何一家现代化企业的办公区域&#xff0c;稳定高速的无线网络已成为像水电一样的基础设施。但不同于家庭Wi-Fi的即插即用&#xff0c;企业级无线网络需要在覆盖范围、接入容量、安全策略和移…...

Linux服务器开机自动挂载网络磁盘(NFS)完整配置流程与排错指南

Linux服务器NFS网络磁盘持久化挂载实战指南 在分布式架构与数据密集型应用场景中&#xff0c;网络文件系统&#xff08;NFS&#xff09;的稳定挂载直接关系到业务连续性。当服务器意外重启后&#xff0c;若共享存储未能自动恢复连接&#xff0c;可能导致应用服务雪崩式瘫痪。本…...