我的LeetCode：https://leetcode cn.com/u/ituring/ 我的LeetCode刷題源碼[GitHub]：https://github.com/izhoujie/Algorithmcii LeetCode 1111. 有效括弧的嵌套深度 題目 __有效括弧字元串__ ...
我的LeetCode：https://leetcode-cn.com/u/ituring/
我的LeetCode刷題源碼[GitHub]：https://github.com/izhoujie/Algorithmcii
LeetCode 1111. 有效括弧的嵌套深度
題目
有效括弧字元串 定義：對於每個左括弧，都能找到與之對應的右括弧，反之亦然。詳情參見題末「有效括弧字元串」部分。
嵌套深度 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
著作權歸領扣網路所有。商業轉載請聯繫官方授權，非商業轉載請註明出處。
解題思路
又是一道讀懂題目死掉一大片腦細胞的題...
簡單講就是把給定的有效的()字元串分成兩部分，使得()的嵌套最低，因為給定的是合法的串，且分割沒有順序要求，
那麼一定可以分成兩部分，且每個部分都是若幹個()的串聯；
題目意思就是這麼簡單！！！
接下來是如何分，題目要求返回一個01分組的數組標識，既然都是成對的，那麼我們可以對(按照第奇數個(分為一部分，第偶數個(分為另一部分，
而對於），按照(的分法反過來分即可，這樣就能保證兩部分的()都是成對的，且一定是若幹個串聯的()；
思路1-根據索引的奇偶和是否(來標記01，）的標記對應為索引+1後處理；
步驟：
- 對於索引index，若當前字元為(，index&1==1標記為1，否則標記為0；
- 若當前字元為)，上面分析過，)的分配按照(反過來分配，那麼我們需要改變index的奇偶性，+1或者-1均可，即（index+1）&1或（index-1）&1
演算法源碼示例
package leetcode;
/**
* @author ZhouJie
* @date 2020年4月1日 下午9:57:59
* @Description: 1111. 有效括弧的嵌套深度
*
*/
public class LeetCode_1111 {
}
class Solution_1111 {
/**
* @author: ZhouJie
* @date: 2020年4月1日 下午9:58:36
* @param: @param seq
* @param: @return
* @return: int[]
* @Description: 1-題目太啰嗦，簡單講就是將()平均分成兩塊，最後它們的深度必都為1，題目要求返回數組形式；
* 步驟：按順序把第奇數個(放一起，把第偶數個(放一起，剩下的)反之分配；
*/
public int[] maxDepthAfterSplit_1(String seq) {
int[] rst = new int[seq.length()];
int index = 0;
for (char c : seq.toCharArray()) {
// 下麵3行代碼都是正確的，取任意一行即可
rst[index++] = c == '(' ? index & 1 : (index + 1) & 1;
// rst[index++] = c == '(' ? index & 1 : (index - 1) & 1;
// rst[index++] = (index & 1) ^ (c == '(' ? 1 : 0);
}
return rst;
}
}
