wordpress国外主题网站模板,中小企业建网站哪个好,最好的免费信息发布平台,wordpress内网和外网【问题描述】
有效括号字符串 定义#xff1a;对于每个左括号#xff0c;都能找到与之对应的右括号#xff0c;反之亦然。详情参见题末「有效括号字符串」部分。嵌套深度 depth 定义#xff1a;即有效括号字符串嵌套的层数#xff0c;depth(A) 表示有效括号字符串 A 的嵌…【问题描述】
有效括号字符串 定义对于每个左括号都能找到与之对应的右括号反之亦然。详情参见题末「有效括号字符串」部分。嵌套深度 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]提示1 text.size 10000有效括号字符串仅由 ( 和 ) 构成的字符串对于每个左括号都能找到与之对应的右括号反之亦然。
下述几种情况同样属于有效括号字符串1. 空字符串2. 连接可以记作 ABA 与 B 连接其中 A 和 B 都是有效括号字符串3. 嵌套可以记作 (A)其中 A 是有效括号字符串
嵌套深度类似地我们可以定义任意有效括号字符串 s 的 嵌套深度 depth(S)1. s 为空时depth() 02. s 为 A 与 B 连接时depth(A B) max(depth(A), depth(B))其中 A 和 B 都是有效括号字符串3. s 为嵌套情况depth(( A )) 1 depth(A)其中 A 是有效括号字符串例如()()和 ()(()()) 都是有效括号字符串嵌套深度分别为 012而 )( 和 (() 都不是有效括号字符串。
【解答思路】
1. 连续的 ‘(’会造成嵌套深度的增加因此对于这种要把他们分到不同的组中。而连续的标准不仅仅是原始字符串中的左右相邻应该还包括中间成对的 ‘’消除后的连续 时间复杂度O(N) 空间复杂度O(N)
public class Solution {public int[] maxDepthAfterSplit(String seq) {int len seq.length();int[] res new int[len];// 嵌套深度栈的当前高度int depth 0;// 在 Java 里seq.charAt(i) 函数会做下标越界检查// 因此先转换成字符数组是常见的做法char[] charArray seq.toCharArray();for (int i 0; i len; i) {// 遇左括号连续括号个数加 1if (charArray[i] () {depth;// %2 也可以写成 1为了保证语义清楚写 %2res[i] depth % 2;} else {// 遇到右括号与之前的嵌套深度栈顶元素的高度分在一组因此先取模再 --res[i] depth % 2;depth--;}}return res;}
}作者liweiwei1419
链接https://leetcode-cn.com/problems/maximum-nesting-depth-of-two-valid-parentheses-strings/solution/qian-tao-shen-du-wan-cheng-gua-hao-pi-pei-wen-ti-s/
【总结】
1.括号匹配 栈思想 2. 感谢leedcodeMamba_ZJP 找工作手撕代码环节一般看风水面试官心情建议还是多刷题训练思维总结方法论分析过程
3.感谢leedcodeliweiwei1419 -如果面试的时候遇到心态上先稳住然后把把题意问清楚说一点自己的想法和思路或者可以从面试官那里得到一点提示。 -如果考到的题目完全不在自己的知识贮备里我个人觉得直接说没有准备这部分的内容好让面试官调整去讨论你会的问题上发现你身上的优点目的还是节约交谈时间是一种建议的办法。
