Leetcode Contest 131

1021. Remove Outermost Parentheses

水题，直接模拟就可以

59 / 59 test cases passed.
Status: Accepted
Runtime: 8 ms
Memory Usage: 9 MB

class Solution {
public:
    string removeOuterParentheses(string S) {

        string ans = "";
        string tmp = "";
        int cnt = 0;
        for(auto&& c : S){
            if(c == '('){
                ++cnt;
                if(cnt == 1){
                    continue;
                }
                
                tmp += "(";
            } else {
                --cnt;
                if(cnt == 0){
                    ans += tmp;
                    tmp = "";
                    continue;
                } 
                
                tmp += ")";
            }
        }
        
        return ans;
    }
};

1022. Sum of Root To Leaf Binary Numbers

水题，注意中间状态值*2的时候可能为爆Int，所以将参数类型设置long

70 / 70 test cases passed.
Status: Accepted
Runtime: 16 ms
Memory Usage: 19.6 MB

class Solution {
public:
    const int INF = 1e9 + 7;
    long ans;
    void dfs(TreeNode* root, long val){
        if(!root) return ;
        
        if(!root->left && !root->right){
            ans += ( (val<<1) + root->val) % INF;
            ans %= INF;
            return ;
        }
        
        
        dfs(root->left, ((val<<1) + root->val) % INF); 
        dfs(root->right, ((val<<1) + root->val) % INF);
    }
    int sumRootToLeaf(TreeNode* root) {
        ans = 0;
        dfs(root, 0);
        return ans;
    }
};

1023. Camelcase Matching

也是个模拟题，匹配失败的条件有：

1. 当query有大写字母时，pattern没有
2. 当pattern有小写字母时，query没有

36 / 36 test cases passed.
Status: Accepted
Runtime: 4 ms
Memory Usage: 8.4 MB

class Solution {
public:
    bool islc(const char a){
        return a >= 'a' && a <= 'z';
    }
    bool match(const string str, const string p){
        int i = 0;
        int j = 0;
        
        
        while(i < str.size() && j < p.size()){
            if(islc(str[i])){
                if(str[i] == p[j]){
                    ++i,++j;
                } else {
                    ++i;
                }
            } else {
                if(str[i] == p[j]){
                    ++i,++j;
                } else {
                    break;
                }
            }
        }
        

        if(j < p.size()) return false;
        
        while(i < str.size() && islc(str[i])) ++i;
        
        if(i < str.size()) return false;
        
        return true;
    }
    
    vector<bool> camelMatch(vector<string>& q, string p) {
        vector<bool> ans(q.size(), false);
        
        
        for(auto i=0;i<q.size(); ++i){
            ans[i] = match(q[i], p);
        }
        
        return ans;
    }
};

1024. Video Stitching

简单dp， 我们假设dp[i]表示 0-i的最小的clips，若 i 在j video clips的interval之间。则有dp[j] = min(dp[j], dp[i] + 1)。

由题意可得：

1. video clips中必须有大于等于T的区间存在
2. video clips中必须有开始为0的区间存在
3. 有相同起始点的区间，我们保持最长的即可，如 [1,3]和[1,9]我们只保留[1,9]

49 / 49 test cases passed.
Status: Accepted
Runtime: 8 ms
Memory Usage: 8.9 MB

class Solution {
public:
    int videoStitching(vector<vector<int>>& c, int T) {
        typedef pair<int,int> ii;
        const int INF = 1e9+7;
        
        vector<ii> p(101, {-1,-1});
        vector<int> dp(101, INF);
        
        int end = 0;
        for(auto&& ci : c){
            if(p[ci[0]].first == -1 || ci[1] - ci[0] > p[ci[0]].second - p[ci[0]].first){
                p[ci[0]] = {ci[0], ci[1]};
            }
            end = max(end, ci[1]);
        }
        
        if(end < T || p[0].first == -1) return -1;
        
        for(int i = 0; i<=p[0].second; ++i) dp[i] = 1;
        
        for(int i=1;i<=T;++i){
            for(int j = 0; j < p.size(); ++j){
                if(p[j].first == -1) continue;
                if(p[j].first > i) break;
                for(int k = p[j].first; k<=p[j].second; ++k){
                    dp[k] = min(dp[k], dp[i] + 1);
                }
            }
        }
        
        return dp[T] >= INF ? -1 : dp[T];
    }
};