微信搜索wordpress内容,成都网站优化指导,怎样做网站维护,中国移动采购与招标网本文涉及知识点
C动态规划
LeetCode1111. 有效括号的嵌套深度
有效括号字符串 定义#xff1a;对于每个左括号#xff0c;都能找到与之对应的右括号#xff0c;反之亦然。详情参见题末「有效括号字符串」部分。 嵌套深度 depth 定义#xff1a;即有效括号字符串嵌套的层…本文涉及知识点
C动态规划
LeetCode1111. 有效括号的嵌套深度
有效括号字符串 定义对于每个左括号都能找到与之对应的右括号反之亦然。详情参见题末「有效括号字符串」部分。 嵌套深度 depth 定义即有效括号字符串嵌套的层数depth(A) 表示有效括号字符串 A 的嵌套深度。详情参见题末「嵌套深度」部分。 有效括号字符串类型与对应的嵌套深度计算方法如下图所示
给你一个「有效括号字符串」 seq请你将其分成两个不相交的有效括号字符串A 和 B并使这两个字符串的深度最小。 不相交每个 seq[i] 只能分给 A 和 B 二者中的一个不能既属于 A 也属于 B 。 A 或 B 中的元素在原字符串中可以不连续。 A.length B.length seq.length 深度最小max(depth(A), depth(B)) 的可能取值最小。 划分方案用一个长度为 seq.length 的答案数组 answer 表示编码规则如下 answer[i] 0seq[i] 分给 A 。 answer[i] 1seq[i] 分给 B 。 如果存在多个满足要求的答案只需返回其中任意 一个 即可。 示例 1 输入seq “(()())” 输出[0,1,1,1,1,0] 示例 2 输入seq “()(())()” 输出[0,0,0,1,1,0,1,1] 解释本示例答案不唯一。 按此输出 A “()()”, B “()()”, max(depth(A), depth(B)) 1它们的深度最小。 像 [1,1,1,0,0,1,1,1]也是正确结果其中 A “()()()”, B “()”, max(depth(A), depth(B)) 1 。 提示 1 seq.size 10000
有效括号字符串 仅由 “(” 和 “)” 构成的字符串对于每个左括号都能找到与之对应的右括号反之亦然。 下述几种情况同样属于有效括号字符串 空字符串 连接可以记作 ABA 与 B 连接其中 A 和 B 都是有效括号字符串 嵌套可以记作 (A)其中 A 是有效括号字符串 嵌套深度 类似地我们可以定义任意有效括号字符串 s 的 嵌套深度 depth(S) s 为空时depth(“”) 0 s 为 A 与 B 连接时depth(A B) max(depth(A), depth(B))其中 A 和 B 都是有效括号字符串 s 为嵌套情况depth(“(” A “)”) 1 depth(A)其中 A 是有效括号字符串 例如“”“()()”和 “()(()())” 都是有效括号字符串嵌套深度分别为 012而 “)(” 和 “(()” 都不是有效括号字符串。
简化后的问题求最小max(a的深度,b的深度)
和本题没直接关系类似而已。本方法可以求解只是太麻烦。 如果s[i]为左括号其权值为1为右括号其权值为-1。p[i]记录s[0…i]的权值和。 pa[i]记录s[0…i]中被a选中的权值和。pb[i]记录s[0…i]中被b选中的权值和。 根据括号的等效条件 条件一 ∀ \forall ∀i,p[i]pa[i],pb[i]都0。 条件二p.back() pa.back() pb.back()都为0。 令f(left,right) 记录s[left…right]中被拆分AB部分的最大深度。 推论一如p[i]等于0则s[0…i]和s[i1…n-1]都是合法括号。 推论二如p[i]等于0则pa[i]和pb[i]都等于0,即a,b都可以通过s[i]拆分。 推论三如果s[i] 0 ,则f(0,n-1) max(f(0,i),f(i1,n-1))。 令 11,i2 g(left,right) 记录s[left…right]i1是A的深度i2是b的深度。确保max(i1,i2)最小。 推论四除了p.back()外p[i]全大于0则 i3,i4 g(left1,right-1) , i1 min(i3,i4)1 i2 max(i3,i4) 如果left right则返回{0,0} 时间复杂度O(nn) ∀ \forall ∀i每层s[i]都只会处理一次。
代码
class Solution {public:int maxDepthAfterSplit(string seq){functionpairint,int(int,int) Do [](int left, int right)- pairint, int {if (left right) { return make_pair(0,0); }int cur 0;for (int i left; i right; i) {cur (( seq[i]) ? 1 : -1;if (cur 0) { auto [i1, i2] Do(left,i);auto [i3, i4] Do(i1, right);vectorint is { i1,i2,i3,i4 };sort(is.begin(), is.end());return { is[1] ,is.back() };}}auto [i1, i2] Do(left1,right-1);return { min(i1,i2) 1,max(i1,i2) };};auto [i1, i2] Do(0, seq.length() - 1);return max(i1, i2);}};单元测试
string seq;TEST_METHOD(TestMethod1){seq (());auto res Solution().maxDepthAfterSplit(seq);AssertEx(1, res);}TEST_METHOD(TestMethod11){seq (()());auto res Solution().maxDepthAfterSplit(seq);AssertEx(1, res);}TEST_METHOD(TestMethod12){seq ()(())();auto res Solution().maxDepthAfterSplit(seq);AssertEx(1, res);}栈
如果用栈判断一个字符串是否是合法括号
左括号入栈。遇到右括号消掉栈顶的左括号如果栈为空则非法。最终栈顶应该为空否则非法。 a,b两个栈分别记录两个子序列遇到左括号放到元素少的栈。遇到右括号消除栈顶元素多的栈。 我们只需要知道栈的元素数量故可以cacb记录两者的数量。 时间复杂度O(n)
代码
class Solution {public:vectorint maxDepthAfterSplit(string seq) {int ca 0,cb0;const int N seq.length();vectorint ret(N);for (int i 0; i N;i ) {if (( seq[i]) {if (ca cb) {ca;ret[i] 0;}else {cb;ret[i] 1;}}else {if (ca cb) {ca--;ret[i] 0;}else {cb--;ret[i] 1;}}}return ret;}};单元测试 int MaxDeq(const string s) {int ret 0,cur0;for (const auto ch : s){cur (( ch) ? 1 : -1;ret max(ret, cur);}return ret;}int Res(const string s, const vectorint res) {string s1, s2;for (int i 0; i s.length(); i) {if (res[i]) {s1 s[i];}else {s2 s[i];}}return max(MaxDeq(s1), MaxDeq(s2));}string seq;TEST_METHOD(TestMethod1){seq (());auto res Solution().maxDepthAfterSplit(seq);AssertEx(1, Res(seq, res));}TEST_METHOD(TestMethod11){seq (()());auto res Solution().maxDepthAfterSplit(seq);AssertEx(1, Res(seq, res));}TEST_METHOD(TestMethod12){seq ()(())();auto res Solution().maxDepthAfterSplit(seq);AssertEx(1, Res(seq, res));}扩展阅读
我想对大家说的话工作中遇到的问题可以按类别查阅鄙人的算法文章请点击《算法与数据汇总》。学习算法按章节学习《喜缺全书算法册》大量的题目和测试用例打包下载。重视操作有效学习明确的目标 及时的反馈 拉伸区难度合适 专注闻缺陷则喜(喜缺)是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛失败反思成功 成功反思成功
视频课程
先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771 如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
