本文涉及知识点
数学 括号匹配
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++**实现。