Leetcode 第144场比赛回顾

零、背景

今天本来正常的在参加比赛，而且发挥超常，前 15 分钟就做了两题，结果不到十一点的时候，工作上各种微信群就在拉电话会议了。
于是只好停止比赛，处理工作上的事情。

看看未来这两个月，发现我都挺忙的。
所以这里给大家请两个月的假，这两个月我就不参加 Leetcode 比赛了。

但是公众号文章还是继续分享比赛的题，每天分享一道题。
另外，上篇文章提到，我做了一本电子书，需要三个月来校验（其实是一个月，前两月工作上太忙了）。
所以三个月后，我校验完毕了，会再公众号告诉大家。
到时候，已经购买的朋友，可以免费领取校验完的第一版。

下面我们来看看这次比赛的四道题吧。

一、相对位置排序

题意：给一个待排序的数组A，以及一个位置打打乱的参考数组B。
如果A的某一个元素在B中，就需要按照B数组的先后顺序进行排序。
如果A的某一个元素不在B中，则需要放在最后面，同时按照大小顺序排序。

思路：map计数即可。
然后先原B数组整有的元素依次放入答案容器，最后遍历map将剩下的元素放入答案。

提示：map的key是按升序排列的。

二、二叉树最深叶子节点的公共祖先

题意：如题，给一个二叉树，求最深叶子节点的公共祖先。
注：最深叶子节点可能有一个，也可能有很多个。

思路：DFS 递归即可。
子树返回两个值，一个是当前子树最深叶子节点的公共祖先，一个是当前子树的最深高度。
当前树根据两个子树的返回值，聚合达到当前树的返回值。

三、最大的工作良好天数

题意：一天工作大于8小时算是工作量饱和。
如果在连续若干天内，工作量饱和的天数大于不饱和天数，则这个天数成为工作良好天数。
求最大的工作良好天数。

思路：问题可以转化一下，工作饱和标记为1，不饱和标记为-1，问题则是求区间和大于 0 的最长区间。
这道题显然需要依次求出i为区间结尾时的最优答案，最终答案则是所有答案里面的最大值。

如果使用O(n^2)暴力求所有区间和的话。
由于数据范围是 10000，在 ACM 中这个做法肯定会超时的， 在 OI 中，这个只能得 30 分的。

我们可以分析数据，假设当前位置i的前缀和是sum[i]。
如果sum[i]>0，那显然整个前缀都是答案。

如果sum[i]<=0，那我们需要找到一个区间sum[j,i]，使得sum[j,i]>0。
因为sum[0,j-1] + sum[j,i] = sum[i]，带入到sum[j,i]中，即可得到sum[i] - sum[0,j-1] > 0。
公式转化一下，即可得到0 >= sum[i] > sum[0,j-1]。

由此，就可以发现，我们的目标是找到最前面的比sum[i]小的位置，从而就可以计算出i的最优答案。
怎么找到这个最优值呢，我甚至想到了树套树，第一层树找到前面所有小于sum[i]的位置集合，第二层树找到这个集合里的最小值。

当然，这个其实有更简单的方式，只是不容易想到而已。

由于整个序列是有1和-1组成，所以前缀和组成的序列是严格连续的。
严格连续的定义指的是相邻的两个前缀和之差肯定是1。

假设最优答案是k，即sum[k] < sum[i] <= 0。
那么在sum[k]肯定是sum[i]-1。

反证法：假设最优答案sum[k] < sum[i]-1，不妨假设位置是L，值sum[L] < sum[i]-1。
由于前缀和的严格连续性，从起始位置到位置L之间肯定存在-1, -2, ..., sum[i]-1, ..., sum[L]的前缀和。
这样，在位置L之前肯定存在另一个位置，值是sum[i]-1，比位置L更优。
假设不成立。

所以，最优答案是sum[i]-1。

PS：对于反正法的题目，其实不是好题目。
因为这个算法算是启发式的算法，面试上不能在这道题上做太多的延伸和扩展。
其实使用逻辑推理也能得到启发式算法，但是这个就需要很强大的分析问题能力了。

四、最少人组成全能团

题意：我们要从 K 个人里面挑选若干人组建一个有 N 个技能组成的全能团队。
问最少选择多少人可以组建这个全能团队。

起初看这道题，很像背包问题，这个人选择或者不选择。
但是会发现状态是若干个技能，没办法储存。
观察技能总个数，只有 16 个，2^16=65536，所以可以使用状态压缩来储存状态。

状态定义：dp[i][j] 为前i个人组建一个技能为j的团队需要的最少人数。
其中j是使用bit位压缩的。

状态转移：对于第i个人可以选择，也可以不选择。
选择了更新 bit状态，不选择了使用旧的bit状态，取最优值。

这样我们就能够进行 递归找到答案了。

由于最终是输出最优答案的路径，所以需要记录状态转移的路径preIndex和preSkill。

五、最后

这次比赛的最后一题，有是经典的动态规划题，专业名称叫做状态压缩。
不知道的大家可以了解一下，非常好用的。

-EOF-