前言
上周周赛因为忘记起床导致没打TAT
本次周赛战绩: rk5，总完成时间20min，还有奖品，好耶！
A 2129.将标题首字母大写
题意
给出一个包含若干个单词的句子，把所有字母变为小写字母，如果单词长度超过 ，则首字母大写。
分析
按照题意模拟即可，这里我们使用 stringstream 类会方便一点。比赛时这题写得比较蠢，浪费了不少时间555。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
string capitalizeTitle(string title) {
stringstream in(title);
string s, ans;
while(in >> s){
for(auto& e: s) e = tolower(e);
if(s.size() > 2) s[0] = toupper(s[0]);
ans += s + " ";
}
ans.pop_back();
return ans;
}
};
|
B 2130. 链表最大孪生和
题意
给定一个链表，设链表长度为 ，求链表第 个元素与第 个元素的和的最大值。
。
分析
把链表存进数组里，然后模拟即可。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution {
public:
int pairSum(ListNode* head) {
vector<int> a;
int ans = 0;
while(head != NULL) a.push_back(head->val), head = head->next;
int n = a.size();
for(int i = 0; i < n; i++){
ans = max(ans, a[i] + a[n - i - 1]);
}
return ans;
}
};
|
C 2131. 连接两字母单词得到的最长回文串
题意
给出 个只有两个字母的单词，求使用这些单词可以拼接出的最长回文串长度。
分析
首先，如果两个单词对称，那么这两个单词用上一定不亏。最后我们会剩下一堆没匹配的单词，我们可以在这些单词里选一个是回文串的单词放在中间（形如 ）。
我赛时的代码十分丑陋=.=
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
int longestPalindrome(vector<string>& words) {
map<string, int> mp, f;
int ok = 0, ans = 0;
for(auto& e: words){
mp[e]++;
auto t = e;
reverse(t.begin(), t.end());
if(t == e) f[e]++, mp[e]--;
else if(mp[t]) mp[e]--, mp[t]--, ans += 4;
}
for(auto& e: f){
int v = e.second;
ans += (v / 2) * 4;
if(v % 2) ok = 1;
}
if(ok) ans += 2;
return ans;
}
};
|
D 2132. 用邮票贴满网格图
题意
给出一个 的 矩阵和一个矩形的高 和宽 ，问每次用这个矩形去覆盖全零的子矩阵能不能把所有的 覆盖。
。
分析
我们只需要判断每一个 能不能被覆盖到。因此可以枚举所有能放矩形的左上角，然后把这个矩阵加一，最后判断每个 的位置上的值是否不为 即可。
判断能不能放矩形需要使用二维前缀和来判断矩阵中有没有 ，矩阵加 需要使用二维差分，最后再跑一遍二维前缀和还原原数组。
总时间复杂度为 。
代码
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
29
30
31
| class Solution {
public:
bool possibleToStamp(vector<vector<int>>& grid, int stampHeight, int stampWidth) {
int n = grid.size(), m = grid[0].size();
vector<vector<int>> sum(n + 2, vector<int>(m + 2)), p(sum);
auto cal = [&](int a, int b, int c, int d){
return sum[c][d] - sum[a - 1][d] - sum[c][b - 1] + sum[a - 1][b - 1];
};
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + grid[i - 1][j - 1];
}
}
for(int i = 1; i + stampHeight - 1 <= n; i++){
for(int j = 1; j + stampWidth - 1 <= m; j++){
int x = i + stampHeight - 1, y = j + stampWidth - 1;
if(!cal(i, j, x, y)){
p[i][j]++, p[x + 1][j]--, p[i][y + 1]--, p[x + 1][y + 1]++;
}
}
}
bool ok = 1;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
p[i][j] += p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1];
if(grid[i - 1][j - 1] == 0 && !p[i][j]) ok = 0;
}
}
return ok;
}
};
|