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
水題，注意中間狀態(tài)值*2的時候可能為爆Int言询，所以將參數(shù)類型設置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
也是個模擬題，匹配失敗的條件有：
- 當query有大寫字母時室抽，pattern沒有
- 當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)风秤。
由題意可得：
-
video clips中必須有大于等于T的區(qū)間存在 -
video clips中必須有開始為0的區(qū)間存在 - 有相同起始點的區(qū)間鳖目，我們保持最長的即可，如 [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];
}
};
