Question

Formatted question description: https://leetcode.ca/all/1111.html


Algorithm

( ( ) ) ( )
0 1 2 3 4 5

0,3 and 4,5 are brackets at the same level, so that the depth of the two parts is 1, and the absolute value of the difference is 0

But if 0, 3 and 1, 2 are put in a group, then the depth of this part is 2, and the depth of the other part is 1, and the absolute value of the difference between the two parts is 1.

Code

Java

    class Solution {
        public int[] maxDepthAfterSplit(String seq) {
            int n = seq.length();
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                if (seq.charAt(i) == '(') {
                    // The left parenthesis of the odd layer is assigned the value 1, and the left parenthesis of the even layer is assigned the value 0
                    arr[i] = i & 1;
                } else {
                    // The index of the right parenthesis of the odd-numbered layer is an even number, and the variable needs to be assigned a value of 1; the index of the right parenthesis of the even-numbered layer is an odd number, and the change amount needs to be assigned a value of 0
                    arr[i] = (i - 1) & 1;
                }
            }
            return arr;
        }
    }


    class Solution222 {
        public int[] maxDepthAfterSplit(String seq) {
            if (seq == null || seq.isEmpty()) {
                return new int[0];
            }
            int[] res = new int[seq.length()];
            Stack<Integer> stack = new Stack<>();
            for (int i = 0; i < seq.length(); i++) {
                if (seq.charAt(i) == '(') {
                    stack.push(i);
                } else {
                    int depth = stack.size();
                    int left = stack.pop();
                    if (depth % 2 == 0) {
                        res[left] = 1;
                        res[i] = 1;
                    }
                }
            }
            return res;
        }
    }

Java

class Solution {
    public int[] maxDepthAfterSplit(String seq) {
        int length = seq.length();
        int[] depths = new int[length];
        int curDepth = -1;
        for (int i = 0; i < length; i++) {
            if (seq.charAt(i) == '(')
                depths[i] = ++curDepth;
            else
                depths[i] = curDepth--;
        }
        int[] split = new int[length];
        for (int i = 0; i < length; i++)
            split[i] = depths[i] % 2;
        return split;
    }
}

All Problems

All Solutions