Leetcode第95场比赛回顾

零、背景

这周五团队一起做了 Leetcode 第 95 场比赛。

做到第二题，我就发现很多人可能到这里就不会了。

做第三题时，我刚开始完全没想法，是先跳过去做第四题的，最后有想法了才把第三题干掉的。

现在来看下比较有难度的一场比赛吧。

PS：这次比赛我是第一次直接在浏览器上做题的，没想到浏览器上敲代码这么方便。

正常比赛下来，只用了一点小时多一点。

明天又比赛了，我再尝试在浏览器上做题试试。

一、链表的中间结点

题号：876

题目：Middle of the Linked List

题意：输出链表的中位数。 如果有两个（偶数长度），输出后面那个。

思路：最简单的方法就是先循环求出链表的长度，计算出答案的位置，然后循环找到那个位置即可。

可以看到，这样需要循环两次才能找到答案。

另一种更快的方法是使用快慢指针，这样循环一遍就可以找到答案了。

二、石子游戏

题号：877

题目：Stone Game

题意：N堆石头排成一行， Alex 和 Lee 两个人轮流拿走一堆石头。

问最终第一个人 Alex 拿到的石头是否可以比第二个多。

规则：有偶数堆石头，每次只能从两头来选一堆。

思路：第一眼看到这道题，我们可以确定这是一道博弈题。

但是不能直接根据递归的子状态来判断是否能赢。

我们只能做到求出子状态的最优值，返回给当前状态，然后求出当前状态的最优值。

以 p[1] p[2]... p[n-1] p[n] 为例。

当前状态是 1~n ， Alex 的目标是在 1~n 的两边选择一堆石头，使得自己的总石头数量最大，我们称为 f(1,n) 。

当 Alex 选择 p[1] 时， Lee 肯定会尽使自己的石头数最大，即 f(2,n) 。

此时 Alex 的石头总数是 sum(1,n) - f(2,n) 。

当 Alex 选择 p[n] 时， Lee 的选择则是 f(1,n-1) 。

此时 Alex 的石头总数是 sum(1,n) - f(1,n-1) 。

面对这两种选择， Alex 肯定选择两个结果里最大的选择。

分析到这里，我们也就把这个博弈过程讲清楚了。

具体用代码实现就是一个 DFS 。

而考虑到子状态存在重复计算，则需要记忆状态。

当然，这两个结合起来，其实就是动态规划了。

赛后，大家讨论的时候，一个同学说：我没找到 Alex 失败的情况，于是直接提交 Alex 永远成功，想看看反例是什么。结果提交后这道题就过了。

然后也有几个同学说自己的算法敲错了，最终也都过了。

那为什么会这样呢？

后来我想了想，想明白了为什么 Alex 必胜 Lee 必败。

而且道理也很简单，不信你看。

总共有偶数堆石头，石头总个数是奇数个。

这说明最终肯定有一个人胜出。

偶数堆按奇偶性分别求和，则要么偶数堆大，要么奇数堆大。

假设石头堆是 1 ~ 2n 。

如果偶数堆大，则 Alex 选择 p[2n] 这堆石头， Lee 只能选择 p[1] 或 p[2n-1] ，即只能选择奇数堆。

之后 Alex 依旧是选择偶数堆，而 Lee 只能选择奇数堆。

最终， Alex 选择的都是偶数堆， Lee 选择的都是奇数堆，这样 Alex 就比 Lee 选的多了。

而对于奇数堆大，是一个道理。

所以第一个选择的人 Alex 必胜了。

这道题算是有史以来代码最短的题了，只需要 return true; 即可。

三、第 N 个神奇数字

题号：878

题目：Nth Magical Number

题意：如果正整数可以被 A 或 B 整除，那么它是神奇的。 返回第 N 个神奇数字。

规则：由于答案可能非常大，返回它模 10^9 + 7 的结果。

思路：看到这道题的第一眼，我是一脸懵逼的，于是就先做下一道题了。

下一道题做完后，只剩这一道题了，就只能分析这道题的特征了。

一分析不要紧，还真找到一个规律：神奇数是有周期的，周期就是 A和B的最小公倍数。

假设 A 和 B 的最小公倍数是 G，其中有 m 个神奇数，分别表示为 f[1],f[2]...f[m] 。

则第 m+1 个神奇数肯定是 G + f[1] ，而第 m + 2 个神奇数肯定是 G + f[1] 。

推广就是，第 N 个神奇数是 G * (N/m) + f[N%m] 。

那接下来的问题就是：怎么求最小公倍数以内的所有神奇数？会不会很多？会不会超时？

面对发自内心的三连问，我想先解决第一个问题：先写出代码提交了再说。

写了一个循环就求出了所有的神奇数，提交后就过了。

然后我思考：为什么没超时？会不会本来就不多？怎么证明？

面对接下来的三连问，其实是一个问题：怎么证明公倍数内的神奇数不多。

简单一思考，发现很容易证明。

与 A 有关的神奇数是 A,2A,...,BA 。

与 B 有关的神奇数是 B,2B,...,AB 。

这样合起来神奇数最多就是 A+B-1 个。

在考虑公约数的问题，神奇数还会比这个还少，即只有 G/A + G/B - 1 个。

而 A 和 B 只有几万，复杂度可以接受，所以这样做不会超时，证闭。

四、盈利计划

题号：879

题目：Profitable Schemes

题意：有 G 个人，有多起犯罪同时发生。

每个犯罪需要 group[i] 个人，可以获取 profit[i] 的利润。

统计到犯罪至少获取的利润是 P,问可能有哪些犯罪发生。

思路：只要题意看懂，就可以看出这是一道基本的动态规划题，甚至是背包问题的变种。

直接把涉及到的变量组装起来，就可以表达出状态： f(G, P, n) 。

含义是前 n 起犯罪里不超过 G 人时至少获得利润 P 的情况数。

此时对第 n 起犯罪分情况讨论。

如果参与犯罪（前提是能），则状态转化为 f(G-g[n], P-p[i], n-1) + check(p-p[i]) 。

check 的含义是到目前未知，利润是否已经够了，够了就算一个答案。

如果不参与犯罪，则状态是 f(G, P, n-1) 。

就这样，就可以求出答案来，复杂度 O(n^3)

五、最后

这次比赛其实蛮有难度的。

除了第一题是水题，第二第四是动态规划，第三是数学题，一般人面对这三道题都会是一道坎。

除非你非常聪明，一般人都需要大量的训练才能熟练的掌握这些题型的。

当然，第二题其实不好，很多人代码敲错了都水过去了。刚才我看了下我的代码，有个地方敲错了，少了个逗号，也过了。

PS：最近我在想怎么把自己做过的题组织起来，以供大家搜索、分类，从而方便的进行专项练习。

目前的选择有两种，一种是在我的网站上实现这个功能，一种是使用知识星球的标签功能，大家怎么看这个呢？

-EOF-