# # Leetcode 第69场双周赛题解

## # Problem A - 将标题首字母大写 (opens new window)

### # 方法一：模拟

• 时间复杂度$\mathcal{O}(|S|)$
• 空间复杂度$\mathcal{O}(|S|)$

class Solution:
def capitalizeTitle(self, title: str) -> str:
return ' '.join([word[0].upper() + word[1:].lower() if len(word) > 2 else word.lower() for word in title.split()])

1
2
3

## # Problem B - 链表最大孪生和 (opens new window)

### # 方法一：暴力

• 时间复杂度$\mathcal{O}(N)$
• 空间复杂度$\mathcal{O}(N)$

class Solution:
def pairSum(self, head: Optional[ListNode]) -> int:
nums = []
while p != None:
nums.append(p.val)
p = p.next
n = len(nums)
return max(nums[i] + nums[n - 1 - i] for i in range(n // 2))

1
2
3
4
5
6
7
8
9

## # Problem C - 连接两字母单词得到的最长回文串 (opens new window)

### # 方法一：哈希表

• 对于两位不同的单词，它需要与它的对称单词构成一对才能放入回文串中；
• 对于两位相同的单词，它可以与它自身构成一对；同时，特别的，有且仅有一次，可以把一个两位相同的单词放在正中间。

• 时间复杂度$\mathcal{O}(N)$
• 空间复杂度$\mathcal{O}(|\sum|^2)$。其中 $\sum$ 表示字母表。

class Solution:
def longestPalindrome(self, words: List[str]) -> int:
same = collections.Counter()
diff = collections.Counter()
for word in words:
if word[0] == word[1]:
same[word] += 1
else:
diff[word] += 1
ans = 0
for word in diff:
rev = word[::-1]
if rev in diff:
ans += min(diff[word], diff[rev]) * 2
for word in same:
ans += same[word] // 2 * 4
same[word] %= 2
for word in same:
if same[word] == 1:
ans += 2
break
return ans

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

## # Problem D - 用邮票贴满网格图 (opens new window)

### # 方法一：贪心+二维前缀和

• 时间复杂度$\mathcal{O}(NM)$
• 空间复杂度$\mathcal{O}(NM)$

class Solution {
vector<vector<int>> build_2d_prefix_sum(vector<vector<int>> &arr) {
int n = arr.size(), m = arr[0].size();
vector<vector<int>> sum(n + 1, vector<int>(m + 1));
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
sum[i + 1][j + 1] = sum[i][j + 1] + sum[i + 1][j] - sum[i][j] + arr[i][j];
return sum;
}

inline int query(vector<vector<int>> &sum, int u, int l, int d, int r) {
return sum[d][r] - sum[d][l - 1] - sum[u - 1][r] + sum[u - 1][l - 1];
}

public:
bool possibleToStamp(vector<vector<int>>& grid, int h, int w) {
int n = grid.size(), m = grid[0].size();
auto sum = build_2d_prefix_sum(grid);

vector<vector<int>> paint(n, vector<int>(m));
for (int i = 0; i + h <= n; ++i)
for (int j = 0; j + w <= m; ++j)
if (grid[i][j] == 0 && query(sum, i + 1, j + 1, i + h, j + w) == 0)
paint[i][j] = 1;

auto psum = build_2d_prefix_sum(paint);
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
if (grid[i][j] == 0 && query(psum, max(1, i - h + 2), max(1, j - w + 2), i + 1, j + 1) == 0)
return false;

return true;
}
};

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