leetcode1111-有效括号的嵌套深度

原题

有效括号字符串 仅由 "(" 和 ")" 构成,并符合下述几个条件之一:

  • 空字符串
  • 连接,可以记作 ABAB 连接),其中 A 和 B 都是有效括号字符串
  • 嵌套,可以记作 (A),其中 A 是有效括号字符串

类似地,我们可以定义任意有效括号字符串 s嵌套深度 depth(S)

  • s 为空时,depth("") = 0
  • sAB 连接时,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]

示例 2:

输入: seq = "()(())()"
输出: [0,0,0,1,1,0,1,1]

提示:

  • 1 <= text.size <= 10000

解法

思想

如果用栈模拟括号匹配,在栈中只存放左括号,当出现右括号的时候,左括号在栈中的下标(用ArrayList模拟栈)即代表了其在原字符串中的嵌套深度,那么要将深度均分,只需要每次出栈的时候将下标为奇偶的括号均分给A和B。

时间复杂度:O(n),n为字符串长度。

代码

class Solution {
    public int[] maxDepthAfterSplit(String seq) {
        List<Integer> stack = new ArrayList<>();
        char[] chars = seq.toCharArray();
        int[] ans = new int[chars.length];
        for(int i = 0;i<chars.length;i++){
            if(chars[i]=='('){
                stack.add(i);
            }else{
                ans[stack.get(stack.size()-1)] = stack.size()%2;
                ans[i] = stack.size()%2;
                stack.remove(stack.size()-1);
            }
        }
        return ans;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode1111-%e6%9c%89%e6%95%88%e6%8b%ac%e5%8f%b7%e7%9a%84%e5%b5%8c%e5%a5%97%e6%b7%b1%e5%ba%a6/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年3月31日 22:27
下一篇 2020年4月1日

相关推荐

  • leetcode1095-山脉数组中查找目标值

    原题 (这是一个 交互式问题 ) 给你一个 山脉数组 mountainArr,请你返回能够使得 mountainArr.get(index) 等于 target 最小 的下标 in…

    算法 2020年4月29日
    0150
  • leetcode264-丑数II

    原题 编写一个程序,找出第 n 个丑数。 丑数就是只包含质因数 2, 3, 5 的正整数。 示例: 输入: n = 10 输出: 12 解释: 1, 2, 3, 4, 5, 6, …

    算法 2020年2月10日
    0190
  • leetcode560-和为K的子数组

    原题 给定一个整数数组和一个整数 k,你需要找到该数组中和为 k 的连续的子数组的个数。 示例 1: 输入: nums = [1,1,1], k = 2 输出: 2 , [1,1]…

    算法 2020年5月15日
    0470
  • leetcode496-下一个更大元素I

    原题 给定两个没有重复元素的数组 nums1 和 nums2 ,其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。 nums…

    算法 2020年1月31日
    0400
  • leetcode38-外观数列

    原题 「外观数列」是一个整数序列,从数字 1 开始,序列中的每一项都是对前一项的描述。前五项如下: 1. 1 2. 11 3. 21 4. 1211 5. 111221 1 被读作…

    算法 2020年4月30日
    0290
  • leetcode31-下一个排列

    原题 整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。 例如,arr = [1,2,3] ,以下这些都可以视作 arr 的排列:[1,2,3]、[1,3,2]、[3,1…

    算法 2022年4月13日
    02583
  • leetcode695-岛屿的最大面积

    原题 给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围…

    算法 2020年3月15日
    01230
  • leetcode1371-每个元音包含偶数次的最长子字符串

    原题 给你一个字符串 s ,请你返回满足以下条件的最长子字符串的长度:每个元音字母,即 'a','e','i','o','u' ,在子字符串中都恰好出现了偶数次。 示例 1: 输入…

    算法 2020年5月20日
    01560
  • 剑指offer13-机器人的运动范围

    原题(来源Leetcode) 地上有一个m行n列的方格,从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动,它每次可以向左、右、上、下…

    算法 2020年4月8日
    0110
  • leetcode123-买卖股票的最佳时机III

    原题 给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 注意: 你不能同时参与多笔交易(你…

    算法 2020年6月16日
    01530

发表回复

登录后才能评论