LeetCode #1111 有效符号的嵌套深度

题目描述

LeetCode #1111 有效符号的嵌套深度

分析

u1s1这道题的翻译着实抽象。。。下面是我认为的几个要点:

  • 有效括号字符串(Valid Parentheses Strings, 后面简写为VPS)中的括号都是前后匹配的,不会出现类似"())"、")("之类的情况;
  • VPSseq,要求将其分为两个子串A、B,它们也需要是VPS;
  • VPS的深度depth
    • 空字符,如"",depth为0;
    • 嵌套,如"(vps)",depth为内部vps的depth+1;
      例:空字符""depth为0,则()depth为1,(())depth为2;
    • 连接,如"vpsA vpsB",depth为vpsA与vpsB的最大值;
  • 题目要求seq的两个子串A、B满足\(MAX(depth(A), depth(B))\)最小

一段VPS的深度取决于它嵌套的层数,而将一段深度为D的VPS拆分为两段深度分别为DA与DB的子串,会有\(D == DA + DB\)(和套娃一个道理?)
因此要使得\(MAX(depth(A), depth(B))\)最小,理论上需要\(DA=DB=\frac{1}{2}D\),而实际情况中D并不一定能等分为DA与DB,一次让二者尽可能接近即可,
代码中要将seq的每嵌套交替分配给子串A和B

算法设计

  • 计数器counter,用来表示还未匹配到")"的"("数
  • 标记位sgn,用来表示下一个(应该分配给哪个子串

程序执行:

  • 当匹配到(:
    • 将sgn加入到result中,0表示这个(分配给了A,1代表分配给了B;
    • 改变sgn--如果下次匹配到的还是(,则说明出现了一层嵌套,要将这个(分给子串B;
    • 增加了一个未匹配的前括号,counter进行一次自加;
  • 当匹配到):
    • 这一位的)应该属于与sgn相异的那个子串,因此将sgn^1加入到result中;
    • 一个前括号得到匹配,counter自减;
    • 如果counter != 0,则说明下个()与刚刚匹配完那个括号为连接关系,把它们分配给同一个子串即可,因此要改变sgn的值;

C++代码实现:

class Solution {
public:
    vector<int> maxDepthAfterSplit(string seq) {
        vector<int> result;
        short counter = 0;
        int sgn = 0;
        for(int i = 0; i < seq.size(); i++){
            if(seq[i] == '('){
                result.push_back(sgn);
                sgn ^= 1;
                counter ++;
            }
            if(seq[i] == ')'){
                result.push_back(sgn ^ 1);
                counter --;
                if(counter != 0){
                    sgn ^= 1;
                }
            }
        }
        return result;
    }
};

运行结果

LeetCode #1111 有效符号的嵌套深度

上一篇:问题 1111: Cylinder圆柱【未完成】


下一篇:取寄存器的值