Leetcode Weekly Contest #131 (1021-1024) 思路与题解
第一次参加周赛 AK 了（哭
不过看了一下我也就只打过4次周赛...
这周的题感觉也都不难，基本都是一次提交就 AC 了，第三题理解错题意了提交 WA 了一次 (
Contest 的链接在这里
1021. Remove Outermost Parentheses
题目大意
输入一个匹配的括号字串，要求输出移除了顶层的结果。
例如这是一个合法的匹配的括号字串 (()())(())，移除顶层之后结果是 ()()()
思路
签到题，没什么好说的，就直接用一个整数加一减一记录即可（
代码
class Solution {
public:
string removeOuterParentheses(string S) {
int flag = 0;
string result = "";
for (auto it : S) {
if (it == '(') flag++;
if (it == ')') flag--;
if (it == '(' && flag == 1) continue;
if (it == ')' && flag == 0) continue;
result += it;
}
return result;
}
};1022. Sum of Root To Leaf Binary Numbers
题目大意
给定一个二叉树，每个节点都有值 0 或 1，输出所有到达叶子节点路径构成的二进制数之和，结果模 10^9 + 7
思路
dfs
代码
/**
* 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 {
long result;
void dfs(TreeNode *root, long prefix) {
if (root == nullptr) return;
prefix = prefix % 1000000007;
prefix = prefix << 1;
if (root->val == 1) {
prefix = prefix + 1;
}
if (root->left == nullptr && root->right == nullptr) {
result += prefix;
result = result % 1000000007;
return;
}
dfs(root->left, prefix);
dfs(root->right, prefix);
}
public:
int sumRootToLeaf(TreeNode* root) {
result = 0;
dfs(root, 0);
return result;
}
};1023. Camelcase Matching
题目大意
输入一个字符串数组和一个模式串，输出一个数组，表示输入的数组每一个元素是否能被模式串匹配。
其中模式串匹配的条件是：模式串通过插入 0 个或多个小写字母使得其与被匹配串相等。 （我一开始理解错题意了噗
思路
就... 直接扫一遍完事儿，也不用什么分治递归，很朴素的做法，复杂度也只是 O(m+n)。
代码
class Solution {
bool isupper(char c) {
return c >= 'A' && c <= 'Z';
}
bool islower(char c) {
return c >= 'a' && c <= 'z';
}
bool query(const string &q, const string &pattern) {
int j = 0, i = 0;
while (i < q.size()) {
if (q[i] == pattern[j]) {
// printf("match: %c - %c\n", q[i], pattern[j]);
++j;
++i;
continue;
}
if (islower(pattern[j])) {
while (i < q.size() && islower(q[i]) && q[i] != pattern[j]) ++i;
if (isupper(q[i]))
return false;
continue;
}
if (isupper(q[i])) return false;
while (islower(q[i]) && i < q.size()) ++i;
}
while (islower(q[i]) && i < q.size()) ++i;
return i == q.size() && j == pattern.size();
}
public:
vector<bool> camelMatch(vector<string>& queries, string pattern) {
vector<bool> result(queries.size(), false);
for (int i = 0; i < queries.size(); ++i) {
result[i] = query(queries[i], pattern);
}
return result;
}
};1024. Video Stitching
题目大意
输入一个由二元数组成的数组和目标数 T，每个元素代表一个片段的起始位置和终止位置，问最少能用多少个片段覆盖 0-T 的区间，如果不可能做到，输出 -1。
思路
先按起始位置升序排序并且去重，去重的规则是：对于相同起始位置的所有元素，只保留终止位置最大的元素。
然后每次取一个起始位置小于等于当前位置且终止位置最大的片段，更新当前位置为其终止位置。
我的代码中其实好像忘记考虑中间有间断点的情况了(也就是说起始一段和最后一段能覆盖到就不考虑中间断开了)，不过好像并没有这样的测试用例（
更严谨一点的话应该在代码中的now = mx前面加一个判断，如果两个相等的话那也说明无解，返回-1。
代码
class Solution {
public:
int videoStitching(vector<vector<int>>& clips, int T) {
sort(clips.begin(), clips.end(), [](const vector<int> &first, const vector<int> &second){
if (first[0] == second[0])
return first[1] < second[1];
return first[0] < second[0];
});
// printf("last: [%d, %d]\n", clips[clips.size() - 1][0], clips[clips.size() - 1][1]);
if (clips[clips.size() - 1][1] < T) return -1;
vector<vector<int>> c;
int last = -1;
for (auto it = clips.rbegin(); it != clips.rend(); ++it) {
if ((*it)[0] != last) {
c.insert(c.begin(), *it);
last = (*it)[0];
} else
continue;
}
// printf("filtered first: [%d, %d]\n", c[0][0], c[0][1]);
// printf("filtered last: [%d, %d]\n", c[c.size() - 1][0], c[c.size() - 1][1]);
if (c[0][0] > 0) return -1;
int now = c[0][1];
int result = 1;
while (now < T) {
int mx = now;
for (auto it: c) {
if (it[0] > now) continue;
mx = max(mx, it[1]);
}
now = mx;
++result;
}
return result;
}
};