leetcode 第 299 场算法比赛 排名122/6036

零、背景

这次比赛的时候，感冒还没好。

公司空调开的比较低，我去外面大街上参加的比赛，很热，快热晕了。

最终没发挥好，最终排名 122，没有进入前百名，遗憾。

一、判断矩阵是否是一个 X 矩阵

题意：给一个矩阵，问矩阵的值是否满足对角线都是非零，非对角线都是非0。

思路：先判断对角线，并把对角线的值修改为一个特殊值。
之后判断整个矩阵来判断非对角线，遇到特殊值说明是对角线忽略即可。

二、统计放置房子的方式数

题意：给两排房子，同一排不能在相邻位置建房子。
问总共有多少中建房子的组合。

思路：两排房子互相独立，所以答案是各自的组合的乘积。

对于每一排，就是典型的动态规划。

方程如下：

f(n) = f(n-1) + f(n-2)

循环计算，取模即可。

三、拼接数组的最大分数

题意：给两个大小相同的数组，问是否划分一个区间[l,r]交换两个数组相同的区间子数组，使得两个数组和的最大值最大。

思路：先理解数组和的最大值最大。
含义是：每一次区间交换，可以得到两个数组和，最大的数组和是这次交换的答案。
所有区间交换中，求答案的最大值。

分析：第一眼看到这道题的数据范围，发现暴力方法会超时。
那显然需要非暴力方法，即二分。
往二分上想，发现确实可以二分。

先假设只求 nums1 的最大值。
枚举交换区间的左边界，我们需要找到所有右边界中，哪个和最大。

公式大概如下：

nums1(1, l) + nums2(l+1, r-1), nums1(r, n)
= num1(1, l) + nums2(1, r-1) + nums1(r, n) - nums2(1, l)

我们的目标是求 nums2(l+1, r-1), nums1(r, n) 的最大值，不容易求。
但是 nums2(1, r-1) + nums1(r, n) 我们可以预处理求出来，存在某种数据结构中，并快速求出最大值了。
再减去常量 nums2(1, l) 就可以计算出答案了。

不过这里需要注意，数据结构中的 r 需要保证大于 l。
即枚举左边界的时候，需要从数据结构中删除上一个非法的区间。

PS：赛后看了其他人的代码，原来可以贪心扫描一遍得到答案。

四、从树中删除边的最小分数

题意：给一个树，每个节点有一个值。
任意删除两条边后，可以把树划分为三个子树。
每个子树的所有节点可以求出一个异或值。
三个子树中最大的异或值与最小的异或值的差是得分。

问删除哪两条边，可以使得得分最小。

思路：只有 1000 个节点，显然可以枚举所有边，求出得分，最后取最小值即可。

那假设我们有两个边了，怎么快速求出三个子树的异或值和。

思路也不难，预处理树转化为有根树，设 0 为根，并求出每个有根子树的异或值。
则问题转化为了一个有根树里拆分出去了两个子树。

两个子树称为 a 和b， 分三种关系：

1、a 是 b 的子树。
2、b 是 a 的子树。
3、a 和 b 没关系。

先来看第三种情况。
a 子树和 b 子树的异或值我们已经预处理出来了。
原有根树拆分出 a 和 b 后，剩余的异或值很容易计算，是 v[0] ^ v[a] ^ v[b]。

而对于其他两种情况，是对称的，这里只展开第一种情况，即 a 是 b 的子树。

a 在 b 子树内部，所以 b 拆分出来后，原有根树的异或值变为了v[0] ^ v[b]。
由于 a 从 b 子树拆出去，所以 b 有根树的异或值变为了 v[b] ^ v[a]。

就这样，我们计算出三个子树的异或值，更新答案即可。

五、最后

这次比赛第二题就来动态规划了，不过比较简单。
第三题可以贪心，不过我第一时间想到的是二分。
第四题枚举边拆分子树，算是图论中的综合题吧。

加油，算法人。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code