【数据结构-合法括号字符串】力扣678. 有效的括号字符串
给你一个只包含三种字符的字符串,支持的字符类型分别是 ‘(’、‘)’ 和 ‘*’。请你检验这个字符串是否为有效字符串,如果是 有效 字符串返回 true 。
有效 字符串符合如下规则:
任何左括号 ‘(’ 必须有相应的右括号 ‘)’。
任何右括号 ‘)’ 必须有相应的左括号 ‘(’ 。
左括号 ‘(’ 必须在对应的右括号之前 ‘)’。
‘*’ 可以被视为单个右括号 ‘)’ ,或单个左括号 ‘(’ ,或一个空字符串 “”。
示例 1:
输入:s = “()”
输出:true
示例 2:
输入:s = “(*)”
输出:true
示例 3:
输入:s = “(*))”
输出:true
提示:
1 <= s.length <= 100
s[i] 为 ‘(’、‘)’ 或 ‘*’
栈
class Solution {
public:bool checkValidString(string s) {stack<int> st1;stack<int> st2;for(int i = 0; i < s.size(); i++){int c = s[i];if(c == '('){st1.push(i);}else if(c == '*'){st2.push(i);}else if(c == ')'){if(!st1.empty()){st1.pop();}else if(!st2.empty()){st2.pop();}else return false;}}while(!st1.empty() && !st2.empty()){int k1 = st1.top();int k2 = st2.top();st1.pop();st2.pop();if(k1 > k2){return false;}}return st1.empty();}
};
时间复杂度:O(n),其中 n 是字符串 s 的长度。需要遍历字符串一次,遍历过程中每个字符的操作时间都是 O(1),遍历结束之后对左括号栈和星号栈弹出元素的操作次数不会超过 n。
空间复杂度:O(n),其中 n 是字符串 s 的长度。空间复杂度主要取决于左括号栈和星号栈,两个栈的元素总数不会超过 n。
这道题,我们可以定义两个栈,一个栈用来储存未匹配的左括号的索引,一个栈用来储存星号的索引。当我们遍历到左括号或者星号的时候,我们就将他的索引推入栈中,当我们遍历到右括号的时候,我们优先将他与左括号进行匹配,没有左括号我们才用星号去匹配。
遍历完字符串了以后,可能会存在还有未匹配的左括号,我们要做的就是将他与星号进行匹配,那么我们就记录栈顶元素,也就是他们各自的索引,由于星号这时候充当的是变成右括号,那么星号的索引必定要大于左括号才可以,如果st1的栈顶索引大于st2的栈顶索引,那么就会返回false,因为这时候找不到一个星号和这个左括号进行匹配。
最后返回st1.empty(),即当st1中的左括号和星号匹配后,依旧还有剩余,那么就是false,如果st1为空,那么就返回true。
贪心
class Solution {
public:bool checkValidString(string s) {int minCount = 0, maxCount = 0;int n = s.size();for(int i = 0; i < n; i++){char c = s[i];if(c == '('){minCount++;maxCount++;}else if(c == ')'){minCount = max(minCount-1, 0);maxCount--;if(maxCount < 0) return false;}else{maxCount++;minCount = max(minCount-1, 0);}}return minCount == 0;}
};
时间复杂度:O(n),其中 n 是字符串 s 的长度。需要遍历字符串一次。
空间复杂度:O(1)。
minCount:表示可能的最低括号数。它考虑了 ‘’ 可以为 ‘)’ 的情况,用于平衡括号。
maxCount:表示可能的最高括号数。它考虑了 '’ 可以为 ‘(’ 的情况,用于平衡括号。
任何情况下,未匹配的左括号数量必须非负,因此当最大值变成负数时,说明没有左括号可以和右括号匹配,返回 false。
相关文章:
【数据结构-合法括号字符串】力扣678. 有效的括号字符串
给你一个只包含三种字符的字符串,支持的字符类型分别是 ‘(’、‘)’ 和 ‘*’。请你检验这个字符串是否为有效字符串,如果是 有效 字符串返回 true 。 有效 字符串符合如下规则: 任何左括号 ‘(’ 必须有相应的右括号 ‘)’。 任何右括号 …...
ThreadX在STM32上的移植:F1,F4通用启动文件tx_initialize_low_level.s
在嵌入式系统开发中,实时操作系统(RTOS)的选择对于系统性能和稳定性至关重要。ThreadX是一种广泛使用的RTOS,它以其小巧、快速和可靠而闻名。在本文中,我们将探讨如何将ThreadX移植到STM32微控制器上,特别是…...
【算法】递归+深搜:814.二叉树剪枝
目录 1、题目链接 2、题目 3、解法(后序遍历) 4、代码 1、题目链接 814.二叉树剪枝(LeetCode) 2、题目 3、解法(后序遍历) 我们这次不使用宏观的观察法,而是从具体实现开始。 题目要求我们,去掉不含1的子树。 对于子树这个…...
spring Framework 特定条件下目录遍历漏洞(CVE-2024-38816)修复
spring Framework 特定条件下目录遍历漏洞(CVE-2024-38816)修复 漏洞描述 CVE-2024-38816: Path traversal vulnerability in functional web frameworks 通过功能性 Web 框架 WebMvc.fn 或 WebFlux.fn 提供静态资源的应用程序容易受到路径遍历攻击。攻…...
ESP32-C3 入门笔记03:VScode + flash_download_tool 下载烧录程序(ESP-IDF + PlatformIO)
ESP32-C3 支持多种烧录方式,主要包括以下几种: VS Code 串口烧录:使用 VS Code 配合 PlatformIO 或 ESP-IDF 插件进行串口烧录。串口连接通常使用 UART 接口,通过 USB 转串口芯片与电脑连接。步骤大致如下: 配置 VS Co…...
Node.js——fs模块-文件重命名和移动
1、在Node.js中,我们可以使用 rename 或 renameSync 来移动或重命名文件或文件夹 2、语法: fs.rename(oldPath,newPath,callback) fs.renameSync(oldPath,newPath) 参数说明: oldPath 文件当前的路径 newPath 文件新的路径 callback 操…...
vue2.0版本引入Element-ui问题解决
作者:fyupeng 技术专栏:☞ https://github.com/fyupeng 项目地址:☞ https://github.com/fyupeng/distributed-blog-system-api 留给读者 使用版本: vue:2.6.14 element-ui:2.15.14 一、问题及解决 1、安装后组件没有生效&#x…...
qt QTableView详解
1、概述 QTableView 是 Qt 框架中的一个高级视图类,用于以表格形式展示二维数据。它基于 QAbstractItemView,并与模型(通常是 QAbstractTableModel 或 QStandardItemModel)结合使用,以实现数据的展示和交互。QTableVi…...
将Notepad++添加到右键菜单【一招实现】
一键添加注册表 复制以下代码保存为 Notepad.reg,将红框内路径修改为自己电脑的“Notepad.exe路径”后,再双击运行即可。 Windows Registry Editor Version 5.00[HKEY_CLASSES_ROOT\*\shell\NotePad] "Notepad" "Icon""D:\\N…...
Nature Methods | 基于流形约束的RNA速度推断精准解析细胞周期动态调节规律
生信碱移 VeloCycle算法 VeloCycle:基于流形约束的RNA速度推断在细胞周期动态中的精准解析 今天给各位老铁们分享一篇于2024年10月31号发表在 Nature Methods [IF: 36.1] 的文章:"Statistical inference with a manifold-constrained RNA velocity…...
在离线环境中使用sealos工具快速部署一套高可用的k8s服务集群
文章目录 项目基础信息工具版本测试环境 下载资源文件下载sealos二进制命令文件下载k8s安装镜像和组件资源下载docker离线安装包下载Docker Registry容器镜像 NFS共享配置coredns服务的DNS解析配置安装配置sealos、k8s服务安装sealos工具导入k8s及相关组件镜像安装 K8s 集群部署…...
ReactPress系列—Next.js 的动态路由使用介绍
ReactPress Github项目地址:https://github.com/fecommunity/reactpress 欢迎提出宝贵的建议,感谢Star。 Next.js 的动态路由使用介绍 Next.js 是一个流行的 React 框架,支持服务端渲染、静态站点生成和动态路由等功能,极大地简化…...
DevOps业务价值流:需求设计最佳实践
DevOps实践正推动着产品快速迭代与高质量交付,但需求设计作为产品开发的关键起点,往往被忽视。它不仅是收集与分析需求的过程,更是将需求转化为可实施产品特性的核心。本文深入探讨DevOps业务价值流中的需求设计,从调研、整理、原…...
A15基于Spring Boot的宠物爱心组织管理系统的设计与实现
🙊作者简介:在校研究生,拥有计算机专业的研究生开发团队,分享技术代码帮助学生学习,独立完成自己的网站项目。 代码可以查看文章末尾⬇️联系方式获取,记得注明来意哦~🌹 赠送计算机毕业设计600…...
RC高通滤波器Bode图分析(传递函数零极点)
RC高通滤波器 我们使得R1K,C1uF;电容C的阻抗为Xc; 传递函数 H ( s ) u o u i R X C R R 1 s C R s R C 1 s R C (其中 s j ω ) H(s)\frac{u_{o} }{u_{i} } \frac{R }{X_{C}R} \frac{R }{\frac{1}{sC}R} \fra…...
SpeechT5 模型
微软开源的 SpeechT5 语音模型,主要包括以下功能 语音转文字:用于自动语音识别(ASR)。文字转语音:用于合成音频(TTS)。语音转语音:用于不同声音之间的转换或进行语音增强。 T5 网络…...
网站用户行为分析:方法、工具与实践
摘要:随着互联网发展,网站竞争激烈,用户行为分析对网站建设与运营至关重要。本文综合介绍了基于服务器日志和客户端收集用户行为数据的方法,包括各自优缺点及相关工具;阐述了网站用户分析的五大常规方法;以…...
医疗医药企业新闻稿怎么写?健康行业品牌宣传背书的报纸期刊杂志媒体有哪些
【本篇由 言同数字全球媒体 原创】在撰写医疗、医学和制药相关稿件时,遵循一定的结构和内容规范至关重要。以下是一些写作建议以及适合发表健康类稿件的报纸、杂志及新闻媒体的推荐。 一、稿件写作结构 标题 原则:简洁、明了,能够准确传达主…...
2024-11-06 问AI: [AI面试题] 人工智能如何用于欺诈检测和网络安全?
文心一言 人工智能在欺诈检测和网络安全领域的应用日益广泛,其强大的数据处理和分析能力为这一领域带来了革命性的变化。以下详细介绍人工智能在欺诈检测和网络安全中的具体应用: 一、欺诈检测 身份认证和访问控制: 通过验证用户的身份信息…...
个人3DCoat设置分享
个人3DCoat设置分享 将当前选择的对象置于屏幕正中显示: /键 版本3DCoat 2023 3DCoat自定义快捷键: Quick Pick: Q Transform: T Primitives: Shift A Cut Off : K Res : Shift Clear Space : Delete 隐藏/显示对象: 点击Sculpt Tree中的眼睛按钮 显示隐…...
网络六边形受到攻击
大家读完觉得有帮助记得关注和点赞!!! 抽象 现代智能交通系统 (ITS) 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 (…...
深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录
ASP.NET Core 是一个跨平台的开源框架,用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录,以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...
【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15
缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下: struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...
【kafka】Golang实现分布式Masscan任务调度系统
要求: 输出两个程序,一个命令行程序(命令行参数用flag)和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽,然后将消息推送到kafka里面。 服务端程序: 从kafka消费者接收…...
docker详细操作--未完待续
docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...
深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法
深入浅出:JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中,随机数的生成看似简单,却隐藏着许多玄机。无论是生成密码、加密密钥,还是创建安全令牌,随机数的质量直接关系到系统的安全性。Jav…...
linux arm系统烧录
1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 (忘了有没有这步了 估计有) 刷机程序 和 镜像 就不提供了。要刷的时…...
页面渲染流程与性能优化
页面渲染流程与性能优化详解(完整版) 一、现代浏览器渲染流程(详细说明) 1. 构建DOM树 浏览器接收到HTML文档后,会逐步解析并构建DOM(Document Object Model)树。具体过程如下: (…...
Python爬虫(一):爬虫伪装
一、网站防爬机制概述 在当今互联网环境中,具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类: 身份验证机制:直接将未经授权的爬虫阻挡在外反爬技术体系:通过各种技术手段增加爬虫获取数据的难度…...
unix/linux,sudo,其发展历程详细时间线、由来、历史背景
sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...
