「リートコード - 双周赛69(2129-2132)」

ジャバ(C++)ソリューション

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
string capitalizeTitle(string title) {
for (int i = 0; i < title.size(); ++i) {
if (title[i] != ' ' && (i == 0 || title[i-1] == ' ') && i != title.size() - 1 && title[i+1] != ' ' && i != title.size() - 2 && title[i+2] != ' ') {
if(title[i] >= 'a' && title[i] <= 'z') {
title[i] += 'A' - 'a';
}
} else if (title[i] != ' ') {
if(title[i] >= 'A' && title[i] <= 'Z') {
title[i] += 'a' - 'A';
}
}
}
return title;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int pairSum(ListNode* head) {
deque<int> d;
for (ListNode* p = head; p; p = p->next) {
d.push_back(p->val);
}
int maxs = 0;
while(!d.empty()) {
maxs = max(maxs, d.front()+d.back());
d.pop_front();
d.pop_back();
}
return maxs;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int longestPalindrome(vector<string>& words) {
vector<vector<int>> v = vector<vector<int>>(26, vector<int>(26));
for (const string &w : words) {
v[w[0]-'a'][w[1]-'a']++;
}
int res = 0;
int extra = 0;
for (int i = 0; i < 26; ++i) {
for (int j = i+1; j < 26; ++j) {
res += min(v[i][j], v[j][i]) * 2;
}
res += v[i][i] / 2 * 2;
extra += v[i][i] % 2;
}
res += extra > 0 ? 1 : 0;
return res * 2;
}
};
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
public:
bool possibleToStamp(vector<vector<int>>& grid, int stampHeight, int stampWidth) {
int n = grid.size(), m = grid[0].size();

vector<vector<int>> s(n, vector<int>(m));
s[0][0] = grid[0][0];
for (int j = 1; j < m; ++j) {
s[0][j] = s[0][j-1] + grid[0][j];
}
for (int i = 1; i < n; ++i) {
s[i][0] = s[i-1][0] + grid[i][0];
for (int j = 1; j < m; ++j) {
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + grid[i][j];
}
}

vector<vector<int>> flag(n, vector<int>(m));
for (int i = 0; i <= n-stampHeight; ++i) {
for (int j = 0; j <= m-stampWidth; ++j) {
int now = s[i+stampHeight-1][j+stampWidth-1];
if (i != 0) now -= s[i-1][j+stampWidth-1];
if (j != 0) now -= s[i+stampHeight-1][j-1];
if (i != 0 && j != 0) now += s[i-1][j-1];
if (now == 0) {
flag[i][j] = 1;
}
}
}

vector<vector<int>> fs(n, vector<int>(m));
fs[0][0] = flag[0][0];
for (int j = 1; j < m; ++j) {
fs[0][j] = fs[0][j-1] + flag[0][j];
}
for (int i = 1; i < n; ++i) {
fs[i][0] = fs[i-1][0] + flag[i][0];
for (int j = 1; j < m; ++j) {
fs[i][j] = fs[i-1][j] + fs[i][j-1] - fs[i-1][j-1] + flag[i][j];
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (grid[i][j] == 0) {
int now = fs[i][j];
if (i >= stampHeight) now -= fs[i-stampHeight][j];
if (j >= stampWidth) now -= fs[i][j-stampWidth];
if (i >= stampHeight && j >= stampWidth) now += fs[i-stampHeight][j-stampWidth];
if (now == 0) {
return false;
}
}
}
}
return true;
}
};

开始水双周赛了,毕竟周赛时间直接不想起床。第一次本来说想java一波,但是确实是太菜了,写不出来,先C++顶一顶了,复盘用java试试,所以还是放在这个目录下吧。

第一题看了题解觉得自己有点蠢,然后看了下java StringBuilder的代码学习一波。

第二题看了都是反转链表做的,但是没说不能用额外空间所以感觉上自己的解法也还过得去。

第三题基本都是哈希思路,学到了java getOrDefault的用法。

第四题我自己的思路是先看能放的都放,先用二维前缀和求每个区域,和为0就是能放,然后把能放的地方再做前缀和,如果对每个空位,能覆盖到他的所有可能区域有任意一个能放,也就是能放的地方的前缀和大于0,那么久返回true。看了下题解的差分解法,学到了而且差分这个东西,包括去滚动恢复什么的。