# # Leetcode 第247场周赛题解

## # Problem A - 两个数对之间的最大乘积差 (opens new window)

### # 方法一：贪心

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

class Solution:
def maxProductDifference(self, nums: List[int]) -> int:
nums.sort()
return nums[-1] * nums[-2] - nums[0] * nums[1]

1
2
3
4

## # Problem B - 循环轮转矩阵 (opens new window)

### # 方法一：模拟

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

class Solution {
public:
vector<vector<int>> rotateGrid(vector<vector<int>>& grid, int k) {
int n = grid.size(), m = grid[0].size();
vector<vector<int>> ans(grid);
for (int i = 0; i < min(n, m) / 2; ++i) {
vector<int> pos;
int p = i, q = i;
pos.emplace_back(p * m + q);
while (p + 1 < n - i) {
p++;
pos.emplace_back(p * m + q);
}
while (q + 1 < m - i) {
q++;
pos.emplace_back(p * m + q);
}
while (p - 1 >= i) {
p--;
pos.emplace_back(p * m + q);
}
while (q - 1 > i) {
q--;
pos.emplace_back(p * m + q);
}
int c = k % pos.size();
for (int j = 0; j < pos.size(); ++j) {
int now = pos[j];
int ni = now / m, nj = now % m;
int pre = pos[(j - c + pos.size()) % pos.size()];
int pi = pre / m, pj = pre % m;
ans[ni][nj] = grid[pi][pj];
}
}

return ans;
}
};

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

## # Problem C - 最美子字符串的数目 (opens new window)

### # 方法一：状态压缩+前缀异或和

• 时间复杂度$\mathcal{O}(NK)$，其中$K=10$
• 空间复杂度$\mathcal{O}(2^K)$

const int K = 10;

class Solution {
public:
long long wonderfulSubstrings(string word) {
int n = word.size();
int state = 0;
vector<int> cnt(1 << K);
cnt[0] = 1;
vector<int> good{0};
for (int i = 0; i < K; ++i)
good.emplace_back(1 << i);

long long ans = 0;
for (char c : word) {
int t = 1 << (c - 'a');
state ^= t;
for (int g : good)
ans += cnt[state ^ g];
cnt[state]++;
}

return ans;
}
};

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

## # Problem D - 统计为蚁群构筑房间的不同顺序 (opens new window)

### # 方法一：树上的动态规划

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

using ll = long long;
const ll MOD = 1e9 + 7;
const int N = 100005;

bool inited = false;
ll fac[N], ifac[N], ans[N];
int sz[N];
ll fexp(ll x, ll y) {
ll ans = 1;
while (y) {
if (y & 1)
ans = ans * x % MOD;
x = x * x % MOD;
y >>= 1;
}
return ans;
}
ll C(int n, int k) {
return fac[n] * ifac[k] % MOD * ifac[n - k] % MOD;
}

void init() {
inited = true;
fac[0] = ifac[0] = 1;
for (int i = 1; i < N; ++i)
fac[i] = fac[i - 1] * i % MOD;
ifac[N - 1] = fexp(fac[N - 1], MOD - 2);
for (int i = N - 2; i >= 1; --i)
ifac[i] = ifac[i + 1] * (i + 1) % MOD;
}

void dfs(int u) {
sz[u] = 0;
for (int v : adj[u]) {
dfs(v);
sz[u] += sz[v];
}

int tot = sz[u];
ans[u] = 1;
for (int v : adj[u]) {
ans[u] = ans[u] * ans[v] % MOD;
ans[u] = ans[u] * C(tot, sz[v]) % MOD;
tot -= sz[v];
}

sz[u]++;
}

class Solution {
public:
int waysToBuildRooms(vector<int>& prevRoom) {
if (!inited)
init();

int n = prevRoom.size();
for (int i = 1; i < n; ++i)

dfs(0);

return ans[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
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
58
59
60
61
62
63
64
65
66