# # Leetcode 第53场双周赛题解

## # Problem A - 长度为三且各字符不同的子字符串 (opens new window)

### # 方法一：暴力

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

class Solution {
public:
int countGoodSubstrings(string s) {
int ans = 0;
for (int i = 0; i + 2 < s.size(); ++i)
if (s[i] != s[i + 1] && s[i] != s[i + 2] && s[i + 1] != s[i + 2])
ans++;
return ans;
}
};

1
2
3
4
5
6
7
8
9
10

Python一行解法：

class Solution:
def countGoodSubstrings(self, s: str) -> int:
return len([i for i in range(len(s) - 2) if len(set(s[i:i + 3])) == 3])

1
2
3

## # Problem B - 数组中最大数对和的最小值 (opens new window)

### # 方法一：贪心

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

class Solution {
public:
int minPairSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
int ans = 0, n = nums.size();
for (int i = 0; i < n / 2; ++i)
ans = max(ans, nums[i] + nums[n - i - 1]);
return ans;
}
};

1
2
3
4
5
6
7
8
9
10

Python一行解法：

class Solution:
def minPairSum(self, nums: List[int]) -> int:
return max(a + b for a, b in zip(sorted(nums), sorted(nums)[::-1]))

1
2
3

## # Problem C - 矩阵中最大的三个菱形和 (opens new window)

### # 方法一：前缀和

$l[i][j][k]$表示从$(i,j)$开始，向左上方走$k$步的和；$r[i][j][k]$表示从$(i,j)$开始，向右上方走$k$步的和。借鉴前缀和的做法，我们可以在$\mathcal{O}(NM\min(N,M))$的时间里求出这些和。

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

class Solution {
public:
vector<int> getBiggestThree(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
int h = min(n, m);
vector<vector<vector<int>>> l(n, vector<vector<int>>(m, vector<int>(h)));
vector<vector<vector<int>>> r(l);
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
l[i][j][0] = r[i][j][0] = grid[i][j];
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j) {
for (int k = 1; i + k < n && j + k < m; ++k)
l[i + k][j + k][k] = l[i + k - 1][j + k - 1][k - 1] + grid[i + k][j + k];
for (int k = 1; i + k < n && j - k >= 0; ++k)
r[i + k][j - k][k] = r[i + k - 1][j - k + 1][k - 1] + grid[i + k][j - k];
}
set<int> pq;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j) {
pq.insert(grid[i][j]);
if (pq.size() > 3)
pq.erase(pq.begin());
for (int k = 1; i - k * 2 >= 0 && j - k >= 0 && j + k < m; ++k) {
int s = l[i][j][k] + r[i][j][k] + r[i - k][j - k][k] + l[i - k][j + k][k] - grid[i][j] - grid[i - k][j - k] - grid[i - k][j + k] - grid[i - 2 * k][j];
pq.insert(s);
if (pq.size() > 3)
pq.erase(pq.begin());
}
}
return vector<int>(pq.rbegin(), pq.rend());
}
};

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

## # Problem D - 两个数组最小的异或值之和 (opens new window)

### # 方法一：状态压缩动态规划

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

class Solution {
public:
int minimumXORSum(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size();
vector<int> dp(1 << n, INT_MAX);
dp[0] = 0;
for (int i = 0; i < n; ++i) {
for (int j = (1 << n) - 1; j >= 0; --j) {
if (dp[j] < INT_MAX) {
for (int k = 0; k < n; ++k) {
if ((j & (1 << k)) == 0) {
int nxt = j ^ (1 << k);
dp[nxt] = min(dp[nxt], dp[j] + (nums1[i] ^ nums2[k]));
}
}
}
}
}
return dp[(1 << n) - 1];
}
};

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 minimumXORSum(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size();
vector<int> dp(1 << n, INT_MAX);
dp[0] = 0;
for (int i = 0; i + 1 < (1 << n); ++i) {
int j = __builtin_popcount(i);
for (int k = 0; k < n; ++k)
if (!(i & (1 << k)))
dp[i ^ (1 << k)] = min(dp[i ^ (1 << k)], dp[i] + (nums1[j] ^ nums2[k]));
}
return dp[(1 << n) - 1];
}
};

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