Songkeys' Blog

Hi! 你好！

LeetCode Weekly Contest 131

发表于 分类于 阅读次数：
本文字数： 8.2k 阅读时长 ≈ 7 分钟

Problem list:

  • Remove Outermost Parentheses
  • Sum of Root To Leaf Binary Numbers
  • Camelcase Matching
  • Video Stitching

This week, I solved the first 3 questions.

1021. Remove Outermost Parentheses

Problem

A valid parentheses string is either empty (""), "(" + A + ")", or A + B, where A and B are valid parentheses strings, and +represents string concatenation. For example, "", "()", "(())()", and "(()(()))" are all valid parentheses strings.

A valid parentheses string S is primitive if it is nonempty, and there does not exist a way to split it into S = A+B, with A and Bnonempty valid parentheses strings.

Given a valid parentheses string S, consider its primitive decomposition: S = P_1 + P_2 + ... + P_k, where P_i are primitive valid parentheses strings.

Return S after removing the outermost parentheses of every primitive string in the primitive decomposition of S.

Example 1:

1
2
3
4
5
Input: "(()())(())"
Output: "()()()"
Explanation: 
The input string is "(()())(())", with primitive decomposition "(()())" + "(())".
After removing outer parentheses of each part, this is "()()" + "()" = "()()()".

Example 2:

1
2
3
4
5
Input: "(()())(())(()(()))"
Output: "()()()()(())"
Explanation: 
The input string is "(()())(())(()(()))", with primitive decomposition "(()())" + "(())" + "(()(()))".
After removing outer parentheses of each part, this is "()()" + "()" + "()(())" = "()()()()(())".

Example 3:

1
2
3
4
5
Input: "()()"
Output: ""
Explanation: 
The input string is "()()", with primitive decomposition "()" + "()".
After removing outer parentheses of each part, this is "" + "" = "".

Note:

  1. S.length <= 10000
  2. S[i] is "(" or ")"
  3. S is a valid parentheses string

https://leetcode.com/contest/weekly-contest-131/problems/remove-outermost-parentheses/

Solution

I was first considering using a stack for this question. But then I found that a boolean is enough to solve this.

The idea is when iterating the given input, store the usable (i.e. not "outer") parentheses by filtering the outer ones. To recognise the outer ones, I use a boolean hasOuter to switch between the states whether there's an left-side outer parentheses ( waiting for the right-side one or not.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    string removeOuterParentheses(string S) {
        string ans = "";
        bool hasOuter = false;
        for (char& c : S) {
            if (!hasOuter) { // outer (
                hasOuter = true;
            } else {
                if (c == ')' && count(ans.begin(), ans.end(), '(') == count(ans.begin(), ans.end(), ')')) { // outer )
                    hasOuter = false;
                } else {
                    ans += c;
                }
            }
        }
        return ans;
    }
};

1022. Sum of Root To Leaf Binary Numbers

Problem

Given a binary tree, each node has value 0 or 1. Each root-to-leaf path represents a binary number starting with the most significant bit. For example, if the path is 0 -> 1 -> 1 -> 0 -> 1, then this could represent 01101 in binary, which is 13.

For all leaves in the tree, consider the numbers represented by the path from the root to that leaf.

Return the sum of these numbers.

Example 1:

img
img
1
2
3
Input: [1,0,1,0,1,0,1]
Output: 22
Explanation: (100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22

Note:

  1. The number of nodes in the tree is between 1 and 1000.
  2. node.val is 0 or 1.
  3. The answer will not exceed 2^31 - 1.

https://leetcode.com/contest/weekly-contest-131/problems/sum-of-root-to-leaf-binary-numbers/

Solution

My idea is quite straightforward: use recursive solution.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int sumRootToLeaf(TreeNode* root) {
        int total = 0;
        calc(root, 0, total);
        return total;
    }
    void calc(TreeNode* node, int sum, int& total) {
        if (node != NULL) {
            sum = (sum * 2 + node->val) % ( (int) pow(10, 9) + 7);
            calc(node->left, sum, total);
            calc(node->right, sum, total);
            if (node->left == NULL && node->right == NULL) { // leaf
                total += sum;
                total %= (int) pow(10, 9) + 7;
            }
        }
    }
};

Pay attention to avoiding overflow of integers.

1023. Camelcase Matching

Problem

A query word matches a given pattern if we can insert lowercase letters to the pattern word so that it equals the query. (We may insert each character at any position, and may insert 0 characters.)

Given a list of queries, and a pattern, return an answer list of booleans, where answer[i] is true if and only if queries[i] matches the pattern.

Example 1:

1
2
3
4
5
6
Input: queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FB"
Output: [true,false,true,true,false]
Explanation: 
"FooBar" can be generated like this "F" + "oo" + "B" + "ar".
"FootBall" can be generated like this "F" + "oot" + "B" + "all".
"FrameBuffer" can be generated like this "F" + "rame" + "B" + "uffer".

Example 2:

1
2
3
4
5
Input: queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FoBa"
Output: [true,false,true,false,false]
Explanation: 
"FooBar" can be generated like this "Fo" + "o" + "Ba" + "r".
"FootBall" can be generated like this "Fo" + "ot" + "Ba" + "ll".

Example 3:

1
2
3
4
Input: queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FoBaT"
Output: [false,true,false,false,false]
Explanation: 
"FooBarTest" can be generated like this "Fo" + "o" + "Ba" + "r" + "T" + "est".

Note:

  1. 1 <= queries.length <= 100
  2. 1 <= queries[i].length <= 100
  3. 1 <= pattern.length <= 100
  4. All strings consists only of lower and upper case English letters.

https://leetcode.com/contest/weekly-contest-131/problems/camelcase-matching/

Solution

For each query, for each character, if it equals to the next unchecked pattern character, increase counter checked by 1, otherwise if it's also an upper case, loop out and mark this query false. If the loop finishes with checked equal to the length of pattern, mark this query true.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<bool> camelMatch(vector<string>& queries, string pattern) {
        vector<bool> ans;
        for (string& query : queries) {
            int checked = 0;
            bool isMatched = true;
            for (char& c : query) {
                if (c == pattern[checked]) {
                    checked++;
                } else if (isupper(c)) {
                    isMatched = false;
                    break;
                }
            }
            ans.push_back(isMatched && checked == pattern.length());
        }
        return ans;
    }
};

The variable isMatched could also be removed:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<bool> camelMatch(vector<string>& queries, string pattern) {
        vector<bool> ans;
        for (string& query : queries) {
            int checked = 0;
            for (char& c : query) {
                if (c == pattern[checked]) {
                    checked++;
                } else if (isupper(c)) {
                    checked = -1;
                    break;
                }
            }
            ans.push_back(checked == pattern.length());
        }
        return ans;
    }
};

1024. Video Stitching

Problem

You are given a series of video clips from a sporting event that lasted T seconds. These video clips can be overlapping with each other and have varied lengths.

Each video clip clips[i] is an interval: it starts at time clips[i][0] and ends at time clips[i][1]. We can cut these clips into segments freely: for example, a clip [0, 7] can be cut into segments [0, 1] + [1, 3] + [3, 7].

Return the minimum number of clips needed so that we can cut the clips into segments that cover the entire sporting event ([0, T]). If the task is impossible, return -1.

Example 1:

1
2
3
4
5
6
7
Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], T = 10
Output: 3
Explanation: 
We take the clips [0,2], [8,10], [1,9]; a total of 3 clips.
Then, we can reconstruct the sporting event as follows:
We cut [1,9] into segments [1,2] + [2,8] + [8,9].
Now we have segments [0,2] + [2,8] + [8,10] which cover the sporting event [0, 10].

Example 2:

1
2
3
4
Input: clips = [[0,1],[1,2]], T = 5
Output: -1
Explanation: 
We can't cover [0,5] with only [0,1] and [0,2].

Example 3:

1
2
3
4
Input: clips = [[0,1],[6,8],[0,2],[5,6],[0,4],[0,3],[6,7],[1,3],[4,7],[1,4],[2,5],[2,6],[3,4],[4,5],[5,7],[6,9]], T = 9
Output: 3
Explanation: 
We can take clips [0,4], [4,7], and [6,9].

Example 4:

1
2
3
4
Input: clips = [[0,4],[2,8]], T = 5
Output: 2
Explanation: 
Notice you can have extra video after the event ends.

Note:

  1. 1 <= clips.length <= 100
  2. 0 <= clips[i][0], clips[i][1] <= 100
  3. 0 <= T <= 100

Solution

1