leetcode 第 413 场算法比赛

零、背景

这次比赛运气比较好，排名 47。

A: 奇偶性判断。
B: 最大堆。
C: 暴力枚举与剪枝。
D: 动态规划。

排名：47
代码地址： https://github.com/tiankonguse/leetcode-solutions/tree/master/contest/4/413

一、检查棋盘方格颜色是否相同

题意：给一个国际象棋棋盘的两个坐标，问坐标的颜色是否相同。

思路：坐标之和奇偶性相同颜色就相同。

二、第 K 近障碍物查询

题意：给一个坐标系，每次加入一个点，问加入之后，离原点第 K 近的点的距离。
距离定义：坐标绝对值之和。

思路：求第K大的值，维护一个大小为 K 的最大堆即可。

三、选择矩阵中单元格的最大得分

题意：给一个矩阵，问每行至多取一个、值互不相同时，可以得到的最大数字和是多少。
数据范围：矩阵大小10*10，值大小[1,100]。

思路：值有100个，压缩为二进制数量最多是 10^10，储存不小。
所以只能暴力搜索加剪枝。

优化：每行去重，从大到小枚举。

剪枝：当前选择之后，假设剩余行数都选择最大值，看是否比最优解小。

优化加剪枝，就可以通过这道题了。

注意事项：枚举的时候，一行可以什么都不选择。

四、查询子数组最大异或值

题意：给一个数组和若干询问。
询问一个数组区间内任意子数组的最大异或值。
异或值定义：不断的进行操作，相邻元素求异或得到新的长度减1的数组，数组大小为 1 时的值就是数组的异或值。

思路：画出数组的异或值矩阵，发现相邻数组之间的异或存在转化关系。

如上图所示，异或值的定义是递归的。
即要求 f(l,r) 的异或值，分为 r-l个步骤。
第一步求所有子数组长度为2的异或值，即求f(l,l+1)、f(l+1,f+2)…f(r-1,r)的异或值。
第二步求所有子数组长度为3的异或值，即求f(l,l+2)、f(l+1,f+3)…f(r-2,r)的异或值。 …
倒数第二步，求所有子数组长度为r-l的异或值,即求f(l,r-1)、f(l+1,r)的异或值。
最后一步，求整个数组的异或值，即求f(l,r)。

面对这个递归定义，我们可以使用动态规划求出任意区间的异或值。

状态定义：f(l,r)为子数组[l,r]的异或值。
状态方程：f(l,r)=f(l,r-1) ^ f(l+1,r)

而对于最大异或值，则可以定义另一个状态来解决。

状态定义：F(l,r) 为子数组[l,r]的任意子数组的最大异或值。
状态方程：F(l,r) = max(f(l,r), F(l,r-1), F(l+1,r))

面对询问，可以提前预处理求出任意区间的答案，然后直接O(1)查询答案即可。

预处理复杂度：O(n^2)
查询复杂度：O(q)

五、最后

这次比赛第四题按定义画一个表格就发现其实不难，而第三题，如果没去尝试暴力搜索，可能就很难通过这道题了。

《完》

-EOF-

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