【每日演算法Day 87】今天我脫單了，所以大家不用做題了！

想啥呢，我哪來的女朋友？今天是愚人節，還是給我老老實實做題吧。

題目鏈接

LeetCode 1111. 有效括弧的嵌套深度[1]

題目描述

題面太長晦澀不想看，請直接跳到最後一段。

有效括弧字元串 僅由 "(" 和 ")" 構成，並符合下述幾個條件之一：

  • 空字元串
  • 連接，可以記作 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，而 ")(" 和 "(()" 都不是有效括弧字元串。

給你一個有效括弧字元串 seq，將其分成兩個不相交的子序列 A 和 B，且 A 和 B 滿足有效括弧字元串的定義（注意：A.length + B.length = seq.length）。

現在，你需要從中選出 任意 一組有效括弧字元串 A 和 B，使 max(depth(A), depth(B)) 的可能取值最小。

返回長度為 seq.length 答案數組 answer ，選擇 A 還是 B 的編碼規則是：如果 seq[i] 是 A 的一部分，那麼 answer[i] = 0。否則，answer[i] = 1。即便有多個滿足要求的答案存在，你也只需返回 一個。

不是我吹牛，我估計一大部分人看完都不知道題目什麼意思。一句話概括就是，給你一個合法的括弧序列，你需要將其拆分成兩個合法的子序列（不連續），使得兩個子序列的括弧嵌套深度較大者盡量的小。

示例1

輸入：  seq = "(()())"  輸出:  [0,1,1,1,1,0]  解釋：  拆成 "()" 和 "()()" ，最大嵌套深度為 1

示例2

輸入：  seq = "()(())()"  輸出:  [0,0,0,1,1,0,1,1]  解釋：  拆成 "()()" 和 "()()" ，最大嵌套深度為 1

說明：

  • 1 <= text.size <= 10000

題解

既然想要兩個子序列的嵌套深度中較大者盡量小，那麼我們最好能夠讓兩個子序列的嵌套深度相同。

再考慮任意一個原序列中嵌套深度為 的合法子序列，我們要想辦法把它拆成兩半。那麼最優的方法肯定是一半嵌套深度為 ，一半是 。這樣兩個子序列中嵌套深度較大值就是 ，而其它任何分法都會導致較大值大於它。

那麼怎麼樣才能對半分呢？這個其實隨意了，但是最為方便的方法就是，嵌套深度為奇數的作為一個子序列，偶數的作為另一個子序列，這樣就對半分了，程式碼還好寫。

具體實現上，我們用一個變數 來表示當前括弧的嵌套深度，那麼遇到左括弧就深度加一，遇到右括弧嵌套深度就是當前的 ，但是遍歷完這個括弧之後，深度要減一，然後嵌套深度為奇數的括弧位置處標記為 1 就行了。

偽程式碼也就是：

if c = '('      cnt := cnt + 1      mask := cnt&1  else      mask := cnt&1      cnt := cnt - 1

簡化

其實我們可以注意到，不管是加一還是減一，奇偶性的變化都是一致的，也就是減一之後的奇偶性和加一之後是相同的。

所以我們把減一也變成加一，那麼不管遇到什麼括弧，都是 加一了，那不就變成了下標 了嗎？

我們把上面的偽程式碼按照這種思路改變一下：

if c = '('      cnt := cnt + 1      mask := cnt&1  else      mask := cnt&1      cnt := cnt + 1

然後用下標 替換掉 :

if c = '('      mask := (i+1)&1  else      mask := i&1

繼續改寫一下，讓形式統一一點：

if c = '('      mask := ~(i&1)  else      mask := i&1

那麼最後就可以把這兩種情況合併了，也就是標記值直接就等於 (i&1)^(c='(') 。

當然我是從程式碼的角度，從奇偶性推過來的，官方題解是直接嚴格證明了正確性：

官方題解：LeetCode 1111. 有效括弧的嵌套深度[2]

程式碼

c++

class Solution {  public:      vector<int> maxDepthAfterSplit(string seq) {          int cnt = 0;          vector<int> res;          for (auto c : seq) {              if (c == '(') {                  res.push_back((++cnt)&1);              } else {                  res.push_back((cnt--)&1);              }          }          return res;      }  };

python

class Solution:      def maxDepthAfterSplit(self, seq: str) -> List[int]:          cnt = 0          res = []          for c in seq:              if c == '(':                  cnt += 1                  res.append(cnt&1)              else:                  res.append(cnt&1)                  cnt -= 1          return res

簡化（c++）

class Solution {  public:      vector<int> maxDepthAfterSplit(string seq) {          vector<int> res;          for (int i = 0, sz = seq.size(); i < sz; ++i) {              res.push_back((i&1)^(seq[i]=='('));          }          return res;      }  };

簡化（python）

class Solution:      def maxDepthAfterSplit(self, seq: str) -> List[int]:          res = []          for i, c in enumerate(seq):              res.append((i&1)^(c=='('))          return res

參考資料

[1]

LeetCode 1111. 有效括弧的嵌套深度: https://leetcode-cn.com/problems/maximum-nesting-depth-of-two-valid-parentheses-strings/

[2]

官方題解：LeetCode 1111. 有效括弧的嵌套深度: https://leetcode-cn.com/problems/maximum-nesting-depth-of-two-valid-parentheses-strings/solution/you-xiao-gua-hao-de-qian-tao-shen-du-by-leetcode-s/

作者簡介：godweiyang，知乎同名，華東師範大學電腦系碩士在讀，方向自然語言處理與深度學習。喜歡與人分享技術與知識，期待與你的進一步交流~

VirMach 便宜 VPS

QNews

QNews