LeetCode周赛299，太卷了！AK了也没能拿到内推机会
LeetCode周赛299，太卷了！AK了也没能拿到内推机会
作者 | 梁唐
出品 | 公众号：Coder梁（ID：Coder_LT）
大家好，日拱一卒，我是梁唐。
今天是周一，我们照惯例来聊聊LeetCode周赛。这一次的比赛赞助商是神策数据，比赛的前300名可以获得公司的内推机会。可惜的是，老梁刚好是306名，差了一点点。
这次的比赛总体来说难度梯度不错，也没有偏题怪题，除了最后一题稍有难度之外，总的来说质量还是非常不错的。
好了，废话不多说，让我们一起来看题吧。
判断矩阵是否是一个 X 矩阵
如果一个正方形矩阵满足下述 全部 条件，则称之为一个 X 矩阵 ：
- 矩阵对角线上的所有元素都 不是 0
- 矩阵中所有其他元素都是 0
给你一个大小为 n x n 的二维整数数组 grid ，表示一个正方形矩阵。如果 grid 是一个 X 矩阵 ，返回 true ；否则，返回 false 。
题解
这题我们需要遍历矩阵内的所有元素，判断是否满足对角线元素全不为0，其他元素全部为0。可以发现元素分为两种，一种是对角线的，必须不为0，一种是非对角线，必须为0。对角线又有两种，一种是正对角线，这种情况满足
(i为行号，j为列号)。另外一种是反对角线，这种情况满足
。
因此，写出代码：
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;
}
};
统计放置房子的方式数
一条街道上共有 n * 2 个 地块 ，街道的两侧各有 n 个地块。每一边的地块都按从 1 到 n 编号。每个地块上都可以放置一所房子。
现要求街道同一侧不能存在两所房子相邻的情况，请你计算并返回放置房屋的方式数目。由于答案可能很大，需要对 109 + 7 取余后再返回。
注意，如果一所房子放置在这条街某一侧上的第 i 个地块，不影响在另一侧的第 i 个地块放置房子。
题解
这题看上去有点唬人，但实际上，我们稍作分析可以发现，街道两边的摆放情况是完全独立的，彼此之间互不影响。所以我们只需要考虑一边的情况，然后再平方即可。
只考虑一边的情况时，我们发现第i位置是否放置房屋有多种情况。首先是i-1处没有房屋时，那么i位置放或者不放都可以。如果i-1放置了房屋，那么i位置只能不放房屋。
我们用dp[i][0]表示第i位置不放房屋的情况总数，dp[i][1]表示第i位置放置房屋的情况。根据上面我们的总结可以得到：
到这里就很明显了，这是一个动态规划的问题。唯一要考虑的是i=0的情况，由于i=0是一个不存在的位置所以它不可能放置房屋，所以dp[0][0]=1, dp[0][1] =0。
由于这题的可能性可能有很多所以需要注意一下数据范围，以免越界。
class Solution {
public:
int countHousePlacements(int n) {
int mod = 1e9 + 7;
int dp[n+2][2];
memset(dp, 0, sizeof dp);
dp[0][0] = 1;
dp[0][1] = 0;
for (int i = 1; i <= n; i++) {
dp[i][0] = (dp[i-1][0] + dp[i-1][1]) % mod;
dp[i][1] = dp[i-1][0] % mod;
}
long long ret = (long long) (dp[n][0] + dp[n][1]) * (long long) (dp[n][0] + dp[n][1]) % mod;
return ret;
}
};
拼接数组的最大分数
给你两个下标从 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 对应元素）。
题解
设想一下，假设我们将nums1中的一部分和nums2中的一部分完成了交换，那么带来的变化有多大？我们假设nums1中交换的总和是sum1，nums2中交换的总和是sum2。那么交换之后，对于nums1来说它的变化就是sum1-sum2。
我们要使得交换之后nums1的和最大，就是要找到最大的sum1-sum2。因为两个数组交换的部分是对应的，长度也是一样的，所以我们可以做一个简单的变形：
进一步可以想到，我们可以造一个新的数组D，其中D[i] = nums1[i]-nums2[i]。所以我们要做的就是求D数组的最大区间和。
最后注意一点，我们最后要找的最大和不一定是nums1也可能是nums2。所以这两种情况我们都要枚举，选择其中较大的即可。
比赛的时候为了顺手，这题用的Python做的：
class Solution:
def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:
def process(nums1, nums2):
n = len(nums1)
diff = [nums1[i] - nums2[i] for i in range(n)]
res, tmp = 0, 0
for i in range(n):
tmp += diff[i]
res = max(res, tmp)
if tmp < 0:
tmp = 0
return sum(nums2) + res
return max(process(nums1, nums2), process(nums2, nums1))
赛后整理了一下代码，写了一个C++版本：
class Solution {
public:
int process(vector<int>& nums1, vector<int> &nums2) {
int n = nums1.size();
int res = 0, tmp = 0, sm = 0;
for (int i = 0; i < n; i++) {
int d = nums2[i] - nums1[i];
tmp += d;
res = max(res, tmp);
if (tmp < 0) tmp = 0;
sm += nums1[i];
}
return sm + res;
}
int maximumsSplicedArray(vector<int>& nums1, vector<int>& nums2) {
return max(process(nums1, nums2), process(nums2, nums1));
}
};
从树中删除边的最小分数
存在一棵无向连通树，树中有编号从 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。
返回在给定树上执行任意删除边方案可能的 最小分数。
题解
这题乍一看比较困难，又是要拆分树，又是要算异或值，好像非常麻烦。尤其是寻找连通分量，我们对此不太熟悉。这里我们可以进行一个简单的转换，树立一个树根，将整体看成是一棵树。
接着，我们先简化问题，我们先假设把树分成两个连通分量。那么可以想见，划分之后的结果只有一种情况：其中一个部分是树中的一棵子树，第二个部分是除去这个子树之后的剩余部分。
题目当中需要我们计算连通分量中所有元素的异或值，关于异或值运算，有两个很好的性质：顺序无关性。若干个数做异或运算，可以随意调换它们的顺序，不会影响最终的结果。第二个性质是可逆性，a ^ b ^ b = a。即同一个数异或两次之后，等价于没有参与运算。
有了这两个性质之后，我们可以推导得到：假设整体所有元素的异或值是x，其中某一棵子树中的元素的异或值是y。那么去除掉这个子树之后剩余部分的异或值就是x ^ y。
将树划分成两个部分的情况我们就算是分析完了，接着思考分成三个部分的情况。三个部分的情况相比于两个更加复杂，体现在划分的连通块之间会存在包含关系。比如：
在这个例子当中，我们选择的第一个连通块是(3, 4)，而第二个连通块是(4)。由于第一个连通块包含了第二个连通块，在计算异或值的时候需要去除掉第二个连通块的部分。
对于包含的情况的判断很简单，我们可以通过子树根之间的父子关系确定。我们预处理树上每一个节点的祖先，如果两个连通块对应子树的其中一个树根是另外一个树根的祖先，那么说明它们之间有包含关系。如果一个连通块包含了另一个连通块，我们在计算所有元素异或值的时候，需要去掉包含的部分。去掉的方式非常简单，和它做异或运算即可。
赛后我看了一下大佬的代码，看到几个优化点，一个是关于判断是否是祖先的逻辑还有更好的方法，就是通过时间戳的方式，对于每个节点只需要存储两个值即可，不再需要存储所有祖先节点。关于时间戳的计算方法这里不做过多赘述了，感兴趣的同学可以去了解一下。大致思想是维护一个节点的开始递归和结束递归的时间戳，通过时间戳的包含关系来判断子树的包含关系。
还有的大佬是分段拆分，先拆分出一棵子树来，再从根节点剩余的部分继续拆分出一棵子树。这样做法的好处是拆分得到的结果是确定的，缺点是对应的异或值不能提前算好，需要临时再使用递归计算。
class Solution {
public:
// 递归，预处理所有子树的异或值，以及所有节点的祖先
// mp存储所有节点为根的子树的所有元素的异或值
// path存储所有节点的祖先
int dfs(vector<vector<int>> &graph, vector<int>& nums, map<int, int>& mp, int f, int u, vector<set<int>>& path, set<int> stp) {
int tmp = nums[u];
stp.insert(u);
for (auto v : graph[u]) {
if (v == f) continue;
path[v] = stp;
tmp = tmp ^ dfs(graph, nums, mp, u, v, path, stp);
}
mp[u] = tmp;
return tmp;
}
// 计算三个值中最大值和最小值的差值
int diff(int x, int y, int z) {
return max(x, max(y, z)) - min(x, min(y, z));
}
int minimumScore(vector<int>& nums, vector<vector<int>>& edges) {
int n = nums.size();
vector<vector<int>> graph(n+1, vector<int>());
map<int, int> sub;
vector<set<int>> path(n+1);
// 创建连接表存储树
for (auto & ed: edges) {
int u = ed[0];
int v = ed[1];
graph[u].push_back(v);
graph[v].push_back(u);
}
set<int> stp;
dfs(graph, nums, sub, -1, 0, path, stp);
int ret = 0x3f3f3f3f;
// 枚举划分出的两个连通块的根节点
for (int i = 1; i < n; i++) {
for (int j = i+1; j < n; j++) {
// 如果j是i的祖先，说明j的连通块包含i
if (path[i].count(j)) {
int p1 = sub[0] ^ sub[j];
int p2 = sub[j] ^ sub[i];
int p3 = sub[i];
ret = min(ret, diff(p1, p2, p3));
// 如果i是j的祖先，说明i的连通块包含j
}else if (path[j].count(i)) {
int p1 = sub[i] ^ sub[j];
int p2 = sub[j];
int p3 = sub[0] ^ sub[i];
ret = min(ret, diff(p1, p2, p3));
}else {
// i和j互相独立
int p1 = sub[i];
int p2 = sub[j];
int p3 = sub[0] ^ p1 ^ p2;
ret = min(ret, diff(p1, p2, p3));
}
}
}
return ret;
}
};
关于本周的周赛就先聊到这里，本期的题目质量还是不错的，即使我在比赛的时候做出了4题赛后复盘的时候依然还是感觉收获很大。对很多算法和思路有了新的认识，真的推荐大家花点时间做一做。尤其是最后一题，质量非常不错！
喜欢本文的话不要忘记三连~
腾讯云开发者
