Leetcode 第 164 场比赛回顾

零、背景

大概从双十一开始，leetcode 上的比赛题风突然全部变了，变得简单了。
有人说这是因为美帝外企跳槽季来了，比赛的题难度与面试难度对齐了。
当然，这种小道消息也没人知道真假，我也不关心真假。

我们关心的是题的题自身的好与坏，以及涉及的算法是否有意思。

下面来看看这几道题吧，都是旧题，之前的比赛中都出现过类似的体型。

一、访问所有点的最小时间

题意：坐标轴上给 n 个点，问按顺序遍历这些点需要的最少时间。
规则：从一个点移动另一个点时，只能垂直上下左右，以及45度斜着走。

思路：如果只能垂直上下左右，那时间就是水平距离加上垂直距离。

由于可以斜着走，每斜着走一步，水平方向和垂直方向都减少一步。
所以我们需要尽可能斜着走。

那能斜着走多少步呢？
水平距离与垂直距离的最小值就是能够斜着走的最大值。

不能斜着走了，则只剩下垂直方向或者水平方向，直线走过去即可。

那最终需要多少步呢？
假设水平需要 a 步， 垂直需要 b 步， 且 a 小于 b。
那么最有答案就是 斜着走 a 步， 垂直走 b-a步， 合起来就是总共走 b 步。

由此就可以得出结论：最优解是垂直距离和水平距离的最大值。

二、统计可以通信的服务器

题意：给一个矩阵，1 代表坐标有一个服务器，0 点没有， 求可以通信的服务器数量。
规则：服务器可以和相同水平线或者垂直线的其他服务器通信。

思路：一个服务器能不能通信，只需要判断水平方向和垂直方向有没有其他服务器。

方法一：最简单的就是按照题意暴力枚举每个服务器是否可以通信。
复杂度分析：矩阵有 n^2 个节点，判断需要 n 次 复杂度：n^3

方法二：进一步分析，可以发现，当一行至少有两个服务器时，这一行的服务器都是可以通信的。
所以可以预处理统计出每行和每列的服务器数量，然后就可以快速知道每个坐标是否可以通信了。

复杂度：n^2

三、搜索推荐系统

题意：给一个字符串数组以及一个待搜索的字符串。
需要设计一个推荐系统，在依次输入待搜索字符串的字母后，从字符串数组中搜索出前缀匹配的字典序最小前三个字符串。

思路：这个类似于电子翻译词典，根据输入的字母，下拉列表会实时动态的变化。

其实这个是典型的字典树，之前我曾在三个比赛中介绍过了。

可是，在之前的比赛中我也介绍了，我不想裸写字典树，而这个还需要维护前驱和后继，更麻烦。
之前我自创的使用数组上二分查找来代替字典树，可以完美的和字典树等价起来，但我也不想敲了。

毕竟代码量有点大，我敲代码速度慢，敲完比赛就结束了。
于是我先做最后一题去了。
最后一题敲完，再一看这道题，发现暴力就可以直接过这道题。

下面就来看看这些方法吧。

方法一：具有前驱和后继的字典树。
复杂度分析：n 个查询，每个查询是前缀长度。 综合复杂度：n^2

方法二：有记忆的字典树
使用字典树裸搜的话，由于每次查询是独立的，导致有很多冗余查询。
冗余的地方在于，这次查询时，前缀实际上已经在上次查询过了。
如果上次查询的信息保存下来，这次就可以在上次的基础上进行查询，这样复杂度就较低了。
综合复杂度：n

方法三：数组加二分查找模拟字典树。
这个方法我在《Leetcode 第133场比赛回顾》里介绍过，这里就不介绍了。
由于是模拟字典树，那就可以和优化后的字典树完全一样。
复杂度： n log(m)

方法四：记忆化数组
这道题的查询很特殊，都是一个字符窜的前缀。
如果带查询的集合排好序的话，前缀长度每增加一，满足条件的集合就缩小一点。

那维护一个满足条件的有序集合的复杂度多高呢？
上一个方法是二分查找，复杂度是 n log(m)
这里没有二分查找了，复杂度就是 n*m 了
但是由于集合大小是 m，累计缩小的个数也不超过 m。
均摊复杂度竟然神奇的转化为了 n + m 。

方法五：暴力二分查找

先对字符串数组排序，题意要求匹配的前三个，那就对整个数组二分查找找到满足条件的第一个。
复杂度： n log(m)

四、停在原地的方案数

题意：给一个长度为 len 的水平线，起始位置在 0， 合法区间是 [0, len)。
每次操作可以左移、右移、原地不动。
经过 n 次操作后，就形成了一个操作路径。
求最终位置在原点 0 的操作路径数。

思路：典型的动态规划题。
在《Leetcode 第 158 场比赛回顾》的第三题 有限制的掷骰子 有点类似。

可以递归实现，也可以递推实现。
而且对于路径相关的动态规划题，递推更容易些。
这次比赛我就是这样实现的。

递推复杂度：n*m

实际上，这类递推的动态规划题，可以使用矩阵幂优化。
在《有限制的随机数（矩阵状态机）》中详细介绍了怎么使用矩阵幂解决这类问题，大概感兴趣的话可以看看。

当然，这道题不适合矩阵幂优化，因为状态太多，移动次数太少。

五、最后

这次比赛的后两题都很适合来当做面试题，大家可以好好研究一下。

PS1：这周比较忙，上一场比赛我迟迟没挤出时间来写文章。
相关题解我就发现免费的算法星球里面了，刚兴趣的可以去看看。

PS2：上次樊登读书抽奖后，中奖者好像没有联系我，奖品三天后就到期了，到时候就作废了。

-EOF-

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