leetcode contest 299

前三题基本上都是套路题了，第四题还是有点难度。

2319. 判断矩阵是否是一个 X 矩阵

题目

如果一个正方形矩阵满足下述全部条件，则称之为一个 X 矩阵：

矩阵对角线上的所有元素都不是 0
矩阵中所有其他元素都是 0
给你一个大小为 n x n 的二维整数数组 grid ，表示一个正方形矩阵。如果 grid 是一个 X 矩阵，返回 true ；否则，返回 false 。

示例 1：

输入：grid = [[2,0,0,1],[0,3,1,0],[0,5,2,0],[4,0,0,2]]
输出：true
解释：矩阵如上图所示。
X 矩阵应该满足：绿色元素（对角线上）都不是 0 ，红色元素都是 0 。
因此，grid 是一个 X 矩阵。

示例 2：

输入：grid = [[5,7,0],[0,3,1],[0,5,0]]
输出：false
解释：矩阵如上图所示。
X 矩阵应该满足：绿色元素（对角线上）都不是 0 ，红色元素都是 0 。
因此，grid 不是一个 X 矩阵。

提示：

n == grid.length == grid[i].length
3 <= n <= 100
0 <= grid[i][j] <= 105

地址

https://leetcode.cn/contest/weekly-contest-299/problems/check-if-matrix-is-x-matrix/

题意

直接遍历

思路

直接遍历判断对角线元素和非对角线元素的值即可。
复杂度分析：

时间复杂度：$O(n^2)$, 其中 $n$ 为矩阵的行数。
空间复杂度：$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;
    }
};

2320. 统计放置房子的方式数

题目

一条街道上共有 n * 2 个地块，街道的两侧各有 n 个地块。每一边的地块都按从 1 到 n 编号。每个地块上都可以放置一所房子。

现要求街道同一侧不能存在两所房子相邻的情况，请你计算并返回放置房屋的方式数目。由于答案可能很大，需要对 109 + 7 取余后再返回。

注意，如果一所房子放置在这条街某一侧上的第 i 个地块，不影响在另一侧的第 i 个地块放置房子。

示例 1：

输入：n = 1
输出：4
解释：
可能的放置方式：
1. 所有地块都不放置房子。
2. 一所房子放在街道的某一侧。
3. 一所房子放在街道的另一侧。
4. 放置两所房子，街道两侧各放置一所。

示例 2：

输入：n = 2
输出：9
解释：如上图所示，共有 9 种可能的放置方式。

提示：

1 <= n <= 104

地址

https://leetcode.cn/contest/weekly-contest-299/problems/count-number-of-ways-to-place-houses/

题意

动态规划

思路

简单的动态规划，设 $x = {0,1,2,3}$ 分别表示道路两侧的房子的状态，则递推公式如下:
$$
dp[i][0] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2] + dp[i-1][3]) \
dp[i][1] = (dp[i-1][0] + dp[i-1][2]) \
dp[i][2] = (dp[i-1][0] + dp[i-1][1]) \
dp[i][3] = (dp[i-1][0]) \
$$
复杂度分析：

时间复杂度：$O(n)$，其中 $n$ 为街道地块的数目。
空间复杂度：$O(n)$，其中 $n$ 为街道地块的数目。

代码

class Solution {
public:
    int countHousePlacements(int n) {
        long long mod = 1e9 + 7;
        vector<vector<long long>> dp(n + 1, vector<long long>(4, 0));
        for (int i = 0; i < 4; i++) {
            dp[1][i] = 1;
        }
        for (int i = 2; i <= n; i++) {
            dp[i][0] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2] + dp[i-1][3]) % mod;
            dp[i][1] = (dp[i-1][0] + dp[i-1][2]) % mod;
            dp[i][2] = (dp[i-1][0] + dp[i-1][1]) % mod;
            dp[i][3] = (dp[i-1][0]) % mod;
        }
        long long res = 0;
        for (int i = 0; i < 4; i++) {
            res = (res + dp[n][i]) % mod;
        }
        return res;
    }
};

2321. 拼接数组的最大分数

题目

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，长度都是 n 。

你可以选择两个整数 left 和 right ，其中 0 <= left <= right < n ，接着交换两个子数组 nums1[left...right] 和 nums2[left...right] 。

例如，设 nums1 = [1,2,3,4,5] 和 nums2 = [11,12,13,14,15] ，整数选择 left = 1 和 right = 2，那么 nums1 会变为 [1,12,13,4,5] 而 nums2 会变为 [11,2,3,14,15] 。
你可以选择执行上述操作一次或不执行任何操作。

数组的分数取 sum(nums1) 和 sum(nums2) 中的最大值，其中 sum(arr) 是数组 arr 中所有元素之和。

返回可能的最大分数。

子数组是数组中连续的一个元素序列。arr[left...right] 表示子数组包含 nums 中下标 left 和 right 之间的元素（含下标 left 和 right 对应元素）。

示例 1：

输入：nums1 = [60,60,60], nums2 = [10,90,10]
输出：210
解释：选择 left = 1 和 right = 1 ，得到 nums1 = [60,90,60] 和 nums2 = [10,60,10] 。
分数为 max(sum(nums1), sum(nums2)) = max(210, 80) = 210 。

示例 2：

输入：nums1 = [20,40,20,70,30], nums2 = [50,20,50,40,20]
输出：220
解释：选择 left = 3 和 right = 4 ，得到 nums1 = [20,40,20,40,20] 和 nums2 = [50,20,50,70,30] 。
分数为 max(sum(nums1), sum(nums2)) = max(140, 220) = 220 。

示例 3：

输入：nums1 = [7,11,13], nums2 = [1,1,1]
输出：31
解释：选择不交换任何子数组。
分数为 max(sum(nums1), sum(nums2)) = max(31, 3) = 31 。

提示：

n == nums1.length == nums2.length
1 <= n <= 105
1 <= nums1[i], nums2[i] <= 104

地址

https://leetcode.cn/contest/weekly-contest-299/problems/maximum-score-of-spliced-array/

题意

最长连续子数组和

思路

仔细一看结果是最长连续子数组和的变形，我们设数组 $arr1$ 为 $[{nums2}[0]-\textit{nums1}[0], {nums2}[1]-\textit{nums1}[1], {nums2}[2]-\textit{nums1}[2], {nums2}[3]-\textit{nums1}[3], \cdots]$。我们只需要找到数组 $arr1$ 中的最大的连续子数组和即可，然后将最大的子数组和加上 $nums1$ 的和，即为将数组 $2$ 替换数组 $1$ 的最大分数，同理我们可以求出数组 $1$ 替换数组 $2$ 的最大分数。
复杂度分析：

时间复杂度：$O(n)$, $n$ 表示数组的长度。
空间复杂度：$O(n)$，$n$ 表示数组的长度。

代码

class Solution {
public:
    int maximumsSplicedArray(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        vector<int> sum1(n + 1);
        vector<int> sum2(n + 1);
        for (int i = 0; i < n; i++) {
            sum1[i + 1] = sum1[i] + nums1[i];
            sum2[i + 1] = sum2[i] + nums2[i];
        }
        int ans = max(sum1[n], sum2[n]);
        vector<int> dp1(n + 1);
        vector<int> dp2(n + 1);
        for (int i = 0; i < n; i++) {
            dp1[i + 1] = max(nums2[i] - nums1[i], dp1[i] + nums2[i] - nums1[i]);
            dp2[i + 1] = max(nums1[i] - nums2[i], dp2[i] + nums1[i] - nums2[i]);
            ans = max(ans, sum1[n] + dp1[i + 1]);
            ans = max(ans, sum2[n] + dp2[i + 1]);
        }
        return ans;
    }
};

2322. 从树中删除边的最小分数

题目

存在一棵无向连通树，树中有编号从 0 到 n - 1 的 n 个节点，以及 n - 1 条边。

给你一个下标从 0 开始的整数数组 nums ，长度为 n ，其中 nums[i] 表示第 i 个节点的值。另给你一个二维整数数组 edges ，长度为 n - 1 ，其中 edges[i] = [ai, bi] 表示树中存在一条位于节点 ai 和 bi 之间的边。

删除树中两条不同的边以形成三个连通组件。对于一种删除边方案，定义如下步骤以计算其分数：

分别获取三个组件每个组件中所有节点值的异或值。
最大异或值和最小异或值的差值就是这一种删除边方案的分数。
例如，三个组件的节点值分别是：[4,5,7]、[1,9] 和 [3,3,3] 。三个异或值分别是 4 ^ 5 ^ 7 = 6、1 ^ 9 = 8 和 3 ^ 3 ^ 3 = 3 。最大异或值是 8 ，最小异或值是 3 ，分数是 8 - 3 = 5 。
返回在给定树上执行任意删除边方案可能的最小分数。

示例 1：

输入：nums = [1,5,5,4,11], edges = [[0,1],[1,2],[1,3],[3,4]]
输出：9
解释：上图展示了一种删除边方案。
- 第 1 个组件的节点是 [1,3,4] ，值是 [5,4,11] 。异或值是 5 ^ 4 ^ 11 = 10 。
- 第 2 个组件的节点是 [0] ，值是 [1] 。异或值是 1 = 1 。
- 第 3 个组件的节点是 [2] ，值是 [5] 。异或值是 5 = 5 。
分数是最大异或值和最小异或值的差值，10 - 1 = 9 。
可以证明不存在分数比 9 小的删除边方案。

示例 2：

输入：nums = [5,5,2,4,4,2], edges = [[0,1],[1,2],[5,2],[4,3],[1,3]]
输出：0
解释：上图展示了一种删除边方案。
- 第 1 个组件的节点是 [3,4] ，值是 [4,4] 。异或值是 4 ^ 4 = 0 。
- 第 2 个组件的节点是 [1,0] ，值是 [5,5] 。异或值是 5 ^ 5 = 0 。
- 第 3 个组件的节点是 [2,5] ，值是 [2,2] 。异或值是 2 ^ 2 = 0 。
分数是最大异或值和最小异或值的差值，0 - 0 = 0 。
无法获得比 0 更小的分数 0 。

提示：

n == nums.length
3 <= n <= 1000
1 <= nums[i] <= 108
edges.length == n - 1
edges[i].length == 2
0 <= ai, bi < n
ai != bi
edges 表示一棵有效的树

地址

https://leetcode.cn/contest/weekly-contest-299/problems/minimum-score-after-removals-on-a-tree/

题意

深度优先搜索

思路

题目非常有意思的说，我们枚举所有可能的两条边即可：

我们首先求出所有节点的异或的值为 $tot$;
设 $dp[x][y]$ 表示去掉节点 $x$ 且以节点 $y$ 为根节点的子树所有节点异或的值;
我们依次枚举去掉 $x$ 且以节点为 $y$ 为根节点的子树中依次去掉一条变 $[a,b]$，此时整个树被分为三部分：
- 以 $y$ 为根节点的子树的节点所有值的异或 $dp[x][y]$;
- 以 $b$ 为根节点的子树的节点所有值的异或 $dp[a][b]$;
- 剩余的部分的节点的值异或为 $tot \oplus dp[x][y] \oplus dp[a][b]$;
- 此时我们即可获分数为：$\max (dp[x][y],dp[a][b], tot \oplus dp[x][y] \oplus dp[a][b]) - \min (dp[x][y],dp[a][b], tot \oplus dp[x][y] \oplus dp[a][b])$。

枚举所有的可能即可。
复杂度分析：

时间复杂度：$n^2$， $n$ 表示节点的数目。
空间复杂度：$n^2$, $n$ 表示节点的数目。

代码

class Solution {
public:
    int dfs(int parent, int root, vector<int> &nums, vector<vector<int>> &adj) {
        int res = nums[root];
        for (auto &neg : adj[root]) {
            if (neg == parent) continue;
            res ^= dfs(root, neg, nums, adj);
        }
        return res;
    }

    int minimumScore(vector<int>& nums, vector<vector<int>>& edges) {
        int n = nums.size();
        int m = edges.size();
        int tot = 0;
        int res = INT_MAX;
        vector<vector<int>> dp(n, vector<int>(n));
        vector<vector<int>> adj(n);
        for (int i = 0; i < n; i++) {
            tot ^= nums[i];
        }
        for (auto &e : edges) {
            adj[e[0]].emplace_back(e[1]);
            adj[e[1]].emplace_back(e[0]);
        }
        for (auto &e : edges) {
            dp[e[0]][e[1]] = dfs(e[0], e[1], nums, adj);
            dp[e[1]][e[0]] = tot ^ dp[e[0]][e[1]];
        }
        for (int i = 0; i < n; i++) {
            vector<bool> visit(n, false);
            visit[i] = true;
            for (auto &neg: adj[i]) {
                queue<int> qu;
                qu.emplace(neg);
                visit[neg] = true;
                while(!qu.empty()) {
                    int curr = qu.front();
                    qu.pop();
                    for (auto & next: adj[curr]) {
                        if (visit[next]) continue;                        
                        res = min(res, max({dp[neg][i], dp[curr][next], tot^dp[neg][i]^dp[curr][next]}) -
                                       min({dp[neg][i], dp[curr][next], tot^dp[neg][i]^dp[curr][next]}));                       
                        visit[next] = true;
                        qu.emplace(next);
                    }
                }
            }
        }        
        return res;
    }
};

欢迎关注和打赏，感谢支持！

关注我的博客: http://mikemeng.org/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 公务程序猿

Tags: 力扣周赛

← leetcode contest 300 leetcode contest biweekly 298 →

扫描二维码，分享此文章