【C++ 数学 括号匹配】2116. 判断一个括号字符串是否有效|2037

本文涉及知识点

数学 括号匹配

LeetCode2116. 判断一个括号字符串是否有效

一个括号字符串是只由 ‘(’ 和 ‘)’ 组成的 非空 字符串。如果一个字符串满足下面 任意 一个条件,那么它就是有效的:
字符串为 ().
它可以表示为 AB(A 与 B 连接),其中A 和 B 都是有效括号字符串。
它可以表示为 (A) ,其中 A 是一个有效括号字符串。
给你一个括号字符串 s 和一个字符串 locked ,两者长度都为 n 。locked 是一个二进制字符串,只包含 ‘0’ 和 ‘1’ 。对于 locked 中 每一个 下标 i :
如果 locked[i] 是 ‘1’ ,你 不能 改变 s[i] 。
如果 locked[i] 是 ‘0’ ,你 可以 将 s[i] 变为 ‘(’ 或者 ‘)’ 。
如果你可以将 s 变为有效括号字符串,请你返回 true ,否则返回 false 。
示例 1:
在这里插入图片描述

输入:s = “))()))”, locked = “010100”
输出:true
解释:locked[1] == ‘1’ 和 locked[3] == ‘1’ ,所以我们无法改变 s[1] 或者 s[3] 。
我们可以将 s[0] 和 s[4] 变为 ‘(’ ,不改变 s[2] 和 s[5] ,使 s 变为有效字符串。
示例 2:

输入:s = “()()”, locked = “0000”
输出:true
解释:我们不需要做任何改变,因为 s 已经是有效字符串了。
示例 3:

输入:s = “)”, locked = “0”
输出:false
解释:locked 允许改变 s[0] 。
但无论将 s[0] 变为 ‘(’ 或者 ‘)’ 都无法使 s 变为有效字符串。
提示:
n == s.length == locked.length
1 <= n <= 105
s[i] 要么是 ‘(’ 要么是 ‘)’ 。
locked[i] 要么是 ‘0’ 要么是 ‘1’ 。

数学 括号匹配

左括号的分数是1,右括号是-1。
v[i] =s[0…i]分值之和。
括号合法的两个条件:
一, ∀ \forall i ,v[i] >=0。
二,v.back() 是0。
三轮循环:
一,从左到右计算v[i],如果v[i] <0。必须:将s[0…i]中的一个右括号改成左括号。改任意一个对条件一和条件二是一样的。我们就改最左的。用队列记录可以修改右括号。
二,计算结束后,如果v.back()>0。则需要将v.back() /2个左括号改成右括号,修改下标大的不劣于下标小的。因为前者对条件一的影响小。用栈可以修改的左括号。
三,判断修改后的s是否合法。
空间复杂度:O(n)
时间复杂度:O(n)

代码

核心代码

class Solution {public:bool canBeValid(string s, string locked) {queue<int> que;stack<int> sta;int sum = 0;for (int i = 0; i < s.length(); i++) {if ('0' == locked[i]) {if (')' == s[i]) { que.emplace(i); }else { sta.emplace(i); }}sum += ('(' == s[i] ? 1 : -1);if (sum < 0) {if (que.empty()) { return false; }s[que.front()] = '(';que.pop();sum += 2;}}sum /= 2;if (sta.size() < sum) { return false; }for (; sum > 0; sum--) {s[sta.top()] = ')';sta.pop();}for (int i = 0; i < s.length(); i++) {					sum += ('(' == s[i] ? 1 : -1);if (sum < 0) {return false;}}return 0 == sum;}};

单元测试

	string s,  locked;TEST_METHOD(TestMethod11){s = "))()))", locked = "010100";auto res = Solution().canBeValid(s, locked);AssertEx(true, res);}TEST_METHOD(TestMethod12){s = "))()))", locked = "010100";auto res = Solution().canBeValid(s, locked);AssertEx(true, res);}TEST_METHOD(TestMethod13){s = ")", locked = "0";auto res = Solution().canBeValid(s, locked);AssertEx(false, res);}TEST_METHOD(TestMethod14){s = "())(()(()(())()())(())((())(()())((())))))(((((((())(()))))(", locked = "100011110110011011010111100111011101111110000101001101001111";auto res = Solution().canBeValid(s, locked);AssertEx(false, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题,可以按类别查阅鄙人的算法文章,请点击《

算法与数据汇总》。|
学习算法:

按章节学习《喜缺全书算法册》,大量

的题目和测试用例,打包下载。重

视操作|
有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注
|闻缺陷则喜(喜缺)是一个美好的

愿望,早发现问题,早修改问题,给老板节约钱。|
| 子墨子言之:事无终始,无务多业。也就是我们

常说的专业的人做专业的事。 |
|如果程序是一条龙,那算法就是他的是睛|
|失败+反思=成功 成功+反

思=成功|

视频课程

先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你

想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系

统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特

殊说明,本算法用**C++**实现。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

计算机毕业设计Python+CNN卷积神经网络考研院校推荐系统 考研分数线预测 考研推荐系统 考研爬虫 考研大数据 Hadoop 大数据毕设 机器学习

温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 作者简介&#xff1a;Java领…

仿真设计|基于51单片机的温室环境监测调节系统

目录 具体实现功能 设计介绍 51单片机简介 资料内容 仿真实现&#xff08;protues8.7&#xff09; 程序&#xff08;Keil5&#xff09; 全部内容 资料获取 具体实现功能 &#xff08;1&#xff09;LCD1602液晶第一行显示当前的光照值及二氧化碳浓度值&#xff0c;第二…

智慧园区如何利用智能化手段提升居民幸福感与环境可持续性

内容概要 在当今社会&#xff0c;随着城市化进程的加快&#xff0c;智慧园区作为一种新兴的城市管理模式&#xff0c;逐渐获得了人们的关注。智慧园区不仅仅是物理空间的规划&#xff0c;更是一种通过智能化手段提升居民幸福感与环境可持续性的综合解决方案。本段将对智慧园区…

Android --- CameraX讲解

预备知识 surface surfaceView SurfaceHolder surface 是什么&#xff1f; 一句话来说&#xff1a; surface是一块用于填充图像数据的内存。 surfaceView 是什么&#xff1f; 它是一个显示surface 的View。 在app中仍在 ViewHierachy 中&#xff0c;但在wms 中可以理解为…

NLP深度学习 DAY5:Sequence-to-sequence 模型详解

Seq2Seq&#xff08;Sequence-to-Sequence&#xff09;模型是一种用于处理输入和输出均为序列任务的深度学习模型。它最初被设计用于机器翻译&#xff0c;但后来广泛应用于其他任务&#xff0c;如文本摘要、对话系统、语音识别、问答系统等。 核心思想 Seq2Seq 模型的目标是将…

Java锁自定义实现到aqs的理解

专栏系列文章地址&#xff1a;https://blog.csdn.net/qq_26437925/article/details/145290162 本文目标&#xff1a; 理解锁&#xff0c;能自定义实现锁通过自定义锁的实现复习Thread和Object的相关方法开始尝试理解Aqs, 这样后续基于Aqs的的各种实现将能更好的理解 目录 锁的…

基于STM32的阿里云智能农业大棚

目录 前言&#xff1a; 项目效果演示&#xff1a; 一、简介 二、硬件需求准备 三、硬件框图 四、CubeMX配置 4.1、按键、蜂鸣器GPIO口配置 4.2、ADC输入配置 4.3、IIC——驱动OLED 4.4、DHT11温湿度读取 4.5、PWM配置——光照灯、水泵、风扇 4.6、串口——esp8266模…

【游戏设计原理】96 - 成就感

成就感是玩家体验的核心&#xff0c;它来自完成一件让自己满意的任务&#xff0c;而这种任务通常需要一定的努力和挑战。游戏设计师的目标是通过合理设计任务&#xff0c;不断为玩家提供成就感&#xff0c;保持他们的参与热情。 ARCS行为模式&#xff08;注意力、关联性、自信…

MySQL CTE:解锁SQL查询新模式

目录 一、CTE 初相识 二、CTE 基础语法 &#xff08;一&#xff09;基本语法结构 &#xff08;二&#xff09;语法规则详解 三、非递归 CTE 应用实例 &#xff08;一&#xff09;单 CTE 简单查询 &#xff08;二&#xff09;多 CTE 联合查询 四、递归 CTE 深入探索 &…

C#,入门教程(12)——数组及数组使用的基础知识

上一篇&#xff1a; C#&#xff0c;入门教程(11)——枚举&#xff08;Enum&#xff09;的基础知识和高级应用https://blog.csdn.net/beijinghorn/article/details/123917587https://blog.csdn.net/beijinghorn/article/details/123917587 数组是一种数据集合&#xff0c;是一组…

【leetcode练习·二叉树】计算完全二叉树的节点数

本文参考labuladong算法笔记[拓展&#xff1a;如何计算完全二叉树的节点数 | labuladong 的算法笔记] 如果让你数一下一棵普通二叉树有多少个节点&#xff0c;这很简单&#xff0c;只要在二叉树的遍历框架上加一点代码就行了。 但是&#xff0c;力扣第第 222 题「完全二叉树的…

低代码系统-产品架构案例介绍、轻流(九)

轻流低代码产品定位为零代码产品&#xff0c;试图通过搭建来降低企业成本&#xff0c;提升业务上线效率。 依旧是从下至上&#xff0c;从左至右的顺序 名词概述运维层底层系统运维层&#xff0c;例如上线、部署等基础服务体系内置的系统能力&#xff0c;发消息、组织和权限是必…

对顾客行为的数据分析:融入2+1链动模式、AI智能名片与S2B2C商城小程序的新视角

摘要&#xff1a;随着互联网技术的飞速发展&#xff0c;企业与顾客之间的交互方式变得日益多样化&#xff0c;移动设备、社交媒体、门店、电子商务网站等交互点应运而生。这些交互点不仅为顾客提供了便捷的服务体验&#xff0c;同时也为企业积累了大量的顾客行为数据。本文旨在…

MSA Transformer

过去的蛋白质语言模型以单个序列为输入&#xff0c;MSA Transformer以多序列比对的形式将一组序列作为输入。该模型将行和列注意力交织在输入序列中&#xff0c;并在许多蛋白质家族中使用mask语言建模目标进行训练。模型的性能远超过了当时最先进的无监督学习方法&#xff0c;其…

QT实现有限元软件操作界面

本系列文章致力于实现“手搓有限元&#xff0c;干翻Ansys的目标”&#xff0c;基本框架为前端显示使用QT实现交互&#xff0c;后端计算采用Visual Studio C。 本篇将二维矩形截面梁单元&#xff08;Rect_Beam2D2Node&#xff09;组成的钢结构桥作为案例来展示软件功能。 也可以…

推荐一款好用的翻译类浏览器扩展插件

给大家推荐一款实用的翻译工具——沉浸式翻译。这是一款免费、高效的AI驱动浏览器扩展插件&#xff0c;能够帮助用户轻松打破语言障碍&#xff0c;享受沉浸式的阅读体验。 主要特性 沉浸式阅读体验&#xff1a;通过智能识别网页主内容区域并进行双语对照翻译&#xff0c;让用户…

ElasticSearch-文档元数据乐观并发控制

文章目录 什么是文档&#xff1f;文档元数据文档的部分更新Update 乐观并发控制 最近日常工作开发过程中使用到了 ES&#xff0c;最近在检索资料的时候翻阅到了 ES 的官方文档&#xff0c;里面对 ES 的基础与案例进行了通俗易懂的解释&#xff0c;读下来也有不少收获&#xff0…

开源的瓷砖式图像板系统Pinry

简介 什么是 Pinry &#xff1f; Pinry 是一个开源的瓷砖式图像板系统&#xff0c;旨在帮助用户轻松保存、标记和分享图像、视频和网页。它提供了一种便于快速浏览的格式&#xff0c;适合喜欢整理和分享多种媒体内容的人。 主要特点 图像抓取和在线预览&#xff1a;支持从网页…

Java 大视界 -- Java 大数据在自动驾驶中的数据处理与决策支持(68)

&#x1f496;亲爱的朋友们&#xff0c;热烈欢迎来到 青云交的博客&#xff01;能与诸位在此相逢&#xff0c;我倍感荣幸。在这飞速更迭的时代&#xff0c;我们都渴望一方心灵净土&#xff0c;而 我的博客 正是这样温暖的所在。这里为你呈上趣味与实用兼具的知识&#xff0c;也…

【数据结构】初识链表

顺序表的优缺点 缺点&#xff1a; 中间/头部的插入删除&#xff0c;时间复杂度效率较低&#xff0c;为O(N) 空间不够的时候需要扩容。 如果是异地扩容&#xff0c;增容需要申请新空间&#xff0c;拷贝数据&#xff0c;释放旧空间&#xff0c;会有不小的消耗。 扩容可能会存在…