寫在前面: 菜雞的我讀題兩小時,終于看懂了。。。
思路:
- 題目意思就是分成 a b兩部分,初始為0
- 每次往a或b中加入seq[i],分給a時answer[i]=0,分給b時answer[i]=1
- 如果seq[i]==’(’ 此時a和b誰深度小就把它加大
- 如果seq[i]==’)’ 此時a和b誰深度大就把它壓小
- 這樣做就能保證a和b深度是差不多的,也就能保證得到a、b兩個字元串的最小深度
- 需要注意:當a和b深度相等時,放誰那裡都行,是以你用第二個樣例測試答案可能會和你跑的結果不一樣
C++版代碼:
class Solution {
public:
vector<int> maxDepthAfterSplit(string seq) {
int a=0,b=0;
vector<int> vec;
for(int i=0;i<seq.length();i++){
if(seq[i]=='('){
if(a<=b){
a++;
vec.push_back(0);
}
else{
b++;
vec.push_back(1);
}
}
else{
if(a>b){
a--;
vec.push_back(0);
}
else{
b--;
vec.push_back(1);
}
}
}
return vec;
}
};
js版代碼:
突然和c++不一樣是因為想起來if else工程師也要寫出優雅的代碼,于是就不寫if else了哈哈,等我有了空檔期我一定要認真啃代碼大全!
var maxDepthAfterSplit = function(seq) {
var a=0,b=0,arr=[];
for(let i of seq){
if(i=='(')
a<=b?(a++,arr.push(0)):(b++,arr.push(1)); //三元運算符代替if else
else
a>b?(a--,arr.push(0)):(b--,arr.push(1));
}
return arr
};
題目位址
題目: 有效括号字元串 定義:對于每個左括号,都能找到與之對應的右括号,反之亦然。詳情參見題末「有效括号字元串」部分。
嵌套深度 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] = 0,seq[i] 分給 A 。
answer[i] = 1,seq[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
有效括号字元串:
僅由 “(” 和 “)” 構成的字元串,對于每個左括号,都能找到與之對應的右括号,反之亦然。
下述幾種情況同樣屬于有效括号字元串:
- 空字元串
- 連接配接,可以記作 AB(A 與 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 是有效括号字元串
例如:"","()()",和 “()(()())” 都是有效括号字元串,嵌套深度分别為 0,1,2,而 “)(” 和 “(()” 都不是有效括号字元串。
來源:力扣(LeetCode)
連結:https://leetcode-cn.com/problems/maximum-nesting-depth-of-two-valid-parentheses-strings
著作權歸領扣網絡所有。商業轉載請聯系官方授權,非商業轉載請注明出處。