# # Leetcode 第49场双周赛题解

## # Problem A - 判断国际象棋棋盘中一个格子的颜色 (opens new window)

### # 方法一：模拟

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

class Solution:
def squareIsWhite(self, coordinates: str) -> bool:
col = ord(coordinates[0]) - ord('a')
row = int(coordinates[1]) - 1
return (col - row) % 2 == 1

1
2
3
4
5

## # Problem B - 句子相似性 III (opens new window)

### # 方法一：贪心

• 时间复杂度为$\mathcal{O}(|S_1|+|S_2|)$
• 空间复杂度$\mathcal{O}(|S_1|+|S_2|)$

class Solution:
def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:
w1 = sentence1.split()
w2 = sentence2.split()
len1 = len(w1)
len2 = len(w2)
l = 0
while l < min(len1, len2) and w1[l] == w2[l]:
l += 1
if l == min(len1, len2):
return True
r = 0
while l + r < min(len1, len2) and w1[len1-1-r] == w2[len2-1-r]:
r += 1
return l + r == min(len1, len2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

## # Problem C - 统计一个数组中好对子的数目 (opens new window)

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

def rev(x):
return int(str(x)[::-1])

class Solution:
def countNicePairs(self, nums: List[int]) -> int:
cnt = collections.Counter()
for num in nums:
cnt[num - rev(num)] += 1
ans = 0
for key in cnt:
ans += cnt[key] * (cnt[key] - 1) // 2
return ans % 1000000007

1
2
3
4
5
6
7
8
9
10
11
12

## # Problem D - 得到新鲜甜甜圈的最多组数 (opens new window)

### # 方法一：动态规划

• 数组或元组
• bitset或长整数
• 混合进制

int freq0[9], freq[9], w[9], f[300000];
class Solution {
public:
int maxHappyGroups(int b, vector<int>& groups) {
for(int i = 0; i < b; ++i) freq0[i] = 0;
for(int i : groups) freq0[i % b]++;
int msum = 1;
for(int i = 1; i < b; ++i) msum *= (freq0[i] + 1);
w[1] = 1;
for(int i = 2; i < b; ++i) w[i] = w[i-1] * (freq0[i-1] + 1);
int last = 0;
for(int i = 1; i < b; ++i) {
freq[i] = (fmask / w[i]) % (freq0[i] + 1);
last = (last + (freq0[i] - freq[i]) * i) % b;
}
for(int c = 1; c < b; ++c) {
}
}
return f[msum-1] + freq0[0];
}
};

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