# # Leetcode 第299场周赛题解

## # Problem A - 判断矩阵是否是一个 X 矩阵 (opens new window)

### # 方法一：模拟

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

class Solution {
public:
bool checkXMatrix(vector<vector<int>>& grid) {
int n = grid.size();
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j) {
if (i == j || i + j == n - 1) {
if (grid[i][j] == 0)
return false;
} else {
if (grid[i][j] != 0)
return false;
}
}
return true;
}
};

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

class Solution:
def checkXMatrix(self, grid: List[List[int]]) -> bool:
n = len(grid)
return all(grid[i][j] == 0 for i in range(n) for j in range(n) if i + j != n - 1 and i != j) and all(grid[i][j] != 0 for i in range(n) for j in range(n) if i + j == n - 1 or i == j)

1
2
3
4

## # Problem B - 统计放置房子的方式数 (opens new window)

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

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

const int MOD = 1e9 + 7;

class Solution {
public:
int countHousePlacements(int n) {
int a = 1, b = 2;
for (int i = 2; i <= n; ++i) {
int tmp = b;
b = (a + b) % MOD;
a = tmp;
}
return 1LL * b * b % MOD;
}
};

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

## # Problem C - 拼接数组的最大分数 (opens new window)

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

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

class Solution {
int solve(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size();
vector<int> d(n);
for (int i = 0; i < n; ++i)
d[i] = nums2[i] - nums1[i];

int hi = 0, now = 0, lo = 0;
for (int di : d) {
now += di;
hi = max(hi, now - lo);
lo = min(lo, now);
}

int ans = 0;
for (int num : nums1)
ans += num;

return ans + hi;
}

public:
int maximumsSplicedArray(vector<int>& nums1, vector<int>& nums2) {
return max(solve(nums1, nums2), solve(nums2, nums1));
}
};

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

## # Problem D - 从树中删除边的最小分数 (opens new window)

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

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

class Solution {
int n, ans, tot;
vector<int> nums, xorsum;

vector<int> dfs(int u, int p) {
vector<int> values;
xorsum[u] = nums[u];
for (int v : adj[u]) {
if (v == p)
continue;

auto vv = dfs(v, u);
xorsum[u] ^= xorsum[v];

for (int vvi : vv) {
for (int vi : values) {
int lo = min(vi, min(vvi, tot ^ vi ^ vvi));
int hi = max(vi, max(vvi, tot ^ vi ^ vvi));
ans = min(ans, hi - lo);
}
}

values.insert(values.end(), vv.begin(), vv.end());
}

if (u != 0) {
for (int vi : values) {
int lo = min(vi, min(xorsum[u] ^ vi, tot ^ xorsum[u]));
int hi = max(vi, max(xorsum[u] ^ vi, tot ^ xorsum[u]));
ans = min(ans, hi - lo);
}
}

values.push_back(xorsum[u]);
return values;
}
public:
int minimumScore(vector<int>& nums, vector<vector<int>>& edges) {
n = nums.size();
xorsum = vector<int>(n);
for (auto &e : edges) {
int u = e[0], v = e[1];
}

tot = 0;
for (int num : nums)
tot ^= num;

this->nums = nums;
ans = INT_MAX;
dfs(0, -1);

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59