leetcode 第 284 场算法比赛

零、背景

可能昨晚睡觉的时候，一开始比较吵。
我以为是隔壁的问题，最终发现是自己房间的问题，断开总电源才不吵了，小丑竟是我自己。
早上又起的早。
比赛的时候，头昏沉沉的。

最后一题我证明了算法的正确性，但是调试一小时始终没过。
打开第一名的代码，发现和我的思路一模一样，连代码都差不多。
于是一行行对比代码，终于找到原因，是一个很低级的错误。

一、找出数组中的所有 K 近邻下标

题意：给一个数组，找出所有的下标，这些下标在 K 距离内，存在值等于 V 的下标。
假设当前下标是 i，则在 [i-K, i+K] 下标范围内寻找目标值 V。

思路：

方法1：先找到所有值为 V 的下标，再讲 [i-K, i+K] 下标全部存取答案集合，最后去重输出。
复杂度：O(N * K)

方法2：使用一个游标记录上次得到的最大答案下标。
然后遍历数组寻找所有值为 V 的下标，对于答案区间 [i-K, i+K] ，从游标的最大值开始遍历，之后更新游标。
复杂度：O(N)

二、统计可以提取的工件

题意：给一个n*n的方格，以及若干不重叠的矩阵，现在对方格进行染色，问哪些矩阵被完整的染色。

思路：

方法1：比赛的时候，我是先处理矩阵的。
每个矩阵分配一个唯一的标号，方格中每个矩阵填充自己的标号。
之后遍历染色列表，对矩阵的标号取反，代表有染色。
之后再遍历每个矩阵，判断说服矩阵的每个坐标是否都染色。

方法2：参考第一名的代码。
先遍历染色列表，对方格进行标记。
之后遍历每个矩阵，判断矩阵的每个坐标是否都标记。

PS：我对矩阵标号是多此一举。

三、K 次操作后最大化顶端元素

题意：给一个元素个数为 N 的数组，左边是栈顶。
操作为下面两种其一。

操作1：如果栈非空，删除栈顶元素。
操作2：删除的元素里面，任选一个放入栈顶。

问 K 次操作之后，栈顶可能的最大值是多少？

思路：分情况讨论。

K 为 0，则没有操作，答案为数组第一个元素。

K 为 1，如果数组大小为 1，则没有答案，否则答案为数组第二个元素。

N 为 1, 一个元素只能不断出栈与入栈。
所以 K 为偶数时答案为第一个元素，为奇数时没答案。

K 小于 N，此时无法把数组所有元素删除。
如果 K 个操作全部删除元素，则栈顶是 第 K+1 个元素。
否则，顶多删除 K-1 个元素，然后把前 K-1 个元素中的最大值加回来变成栈顶。
所以，这种情况下，答案是 [1, K-1] 和 K+1 里面的最大值。

K 等于 N， K 个元素全部删除就没有答案了，所以不能全部删除。
不全部删除，就是顶多删除 K-1 个元素，然后把前 K-1个元素里的最大值加回来变成栈顶。
所以，答案是 [1, K-1] 里面的最大值。

K 大于 N，此时数组所有元素都可以删除，然后把最大值加回来即可。
剩余的操作可以不断删除再添加，如果还剩一次，可以先加入其他元素，再添加最大值。
所以，此时答案是数组的最大值。

四、得到要求路径的最小带权子图

题意：给一个带权有向图，一个子图需要满足两个源点 S1 与 S2 到 目标 D 存在路径。
问最小子图权值和是多少。

思路：显然，子图只需要两个路径的并集即可。

路径合并时，有公共路径。
可以证明，公共路径是某个顶点与目标顶点的一条路径。

假设我们知道了公共路径的顶点 C ，则问题转化成了三个最短路问题：

-）S1 到 C 的最短路。
-）S2 到 C 的最短路。
-）C 到 D 的最短路。

题目给的是有向图，可以直接求出 S1 和 S2 到所有顶点的最短路。
而对于 C 到 D 的最短路，需要反转有向图的方向，然后就可以求出 D 到所有点的最短路了。

之后枚举 C，求最优值即可。

PS：求最短路的时候，有个地方变量定义的 32 位，导致越界了。

五、最后

这次比赛比较可惜。

最后一题不难，但是因为自己实现单源最短路的时候，中间更改过类型，有个地方漏了，最终导致越界。

以后所有值我决定都使用 long long 了。

加油，算法人。

《完》

-EOF-

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