# # Leetcode 第244场周赛题解

## # Problem A - 判断矩阵经轮转后是否一致 (opens new window)

### # 方法一：模拟

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

class Solution {
vector<vector<int>> rotate(vector<vector<int>> &a) {
int n = a.size();
vector<vector<int>> ans(n, vector<int>(n));
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
ans[j][n - 1 - i] = a[i][j];
return ans;
}
public:
bool findRotation(vector<vector<int>>& mat, vector<vector<int>>& target) {
int n = mat.size();
vector<vector<int>> r(mat);
for (int i = 0; i < 4; ++i) {
bool same = true;
for (int p = 0; p < n; ++p)
for (int q = 0; q < n; ++q)
if (r[p][q] != target[p][q])
same = false;
if (same)
return true;
r = rotate(r);
}
return false;
}
};

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

import numpy as np

class Solution:
def findRotation(self, mat: List[List[int]], target: List[List[int]]) -> bool:
source = np.array(mat)
target = np.array(target)
for i in range(4):
if (source == target).all():
return True
source = np.rot90(source)
return False

1
2
3
4
5
6
7
8
9
10
11

## # Problem B - 使数组元素相等的减少操作次数 (opens new window)

### # 方法一：排序

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

class Solution {
public:
int reductionOperations(vector<int>& nums) {
map<int, int> cnt;
for (int num : nums)
cnt[num]++;
int ans = 0, acc = 0;
for (auto it = cnt.rbegin(); it != cnt.rend(); ++it) {
int f = it->second;
ans += acc;
acc += f;
}
return ans;
}
};

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

## # Problem C - 使二进制字符串字符交替的最少反转次数 (opens new window)

### # 方法一：滑动窗口

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

class Solution:
def minFlips(self, s: str) -> int:
n = len(s)
t = s + s
a = '01' * n
b = '10' * n
ans = n
da = 0
db = 0
for i in range(n * 2):
if t[i] != a[i]:
da += 1
if t[i] != b[i]:
db += 1
if i >= n:
if t[i - n] != a[i - n]:
da -= 1
if t[i - n] != b[i - n]:
db -= 1
if i >= n - 1:
ans = min(ans, da, db)
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}((N+K)\log N+K\log K)$，其中$K$是所有供应商的箱子总数。
• 空间复杂度$\mathcal{O}(1)$

using ll = long long;
const ll MOD = 1e9 + 7;

class Solution {
public:
int minWastedSpace(vector<int>& packages, vector<vector<int>>& boxes) {
ll ans = LLONG_MAX;
sort(packages.begin(), packages.end());
ll sum = 0;
for (int package : packages)
sum += package;
for (auto &box : boxes) {
sort(box.begin(), box.end());
if (packages.back() > box.back())
continue;
ll used = 0;
ll ptr = 0;
for (int b : box) {
auto it = upper_bound(packages.begin(), packages.end(), b);
if (it != packages.begin()) {
it--;
int idx = it - packages.begin();
used += 1LL * b * (idx + 1 - ptr);
ptr = idx + 1;
}
}
ans = min(ans, used - sum);
}

return ans == LLONG_MAX ? -1 : ans % MOD;
}
};

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