leetcode 第182场算法比赛

零、背景

今天正常的做比赛，发现前三题都是大水题，第四题是个我最喜欢的DFA题（高级的动态规划题）。

想着这次应该可以在半个小时内做完比赛，结果做了两道题后工作上有点事，再回来的时候就要结束比赛了。

七八年前，我非常热衷于DFA算法题，还整理了几个模板，感兴趣的可以后台回复“ACM模板”获取。

一、幸运数字

题意：给一个数组，如果一个数字出现的次数刚好等于数字的值，则成为这个数字为幸运数字。

思路：map 统计即可。

二、组队的数目

题意：给一个数组，任意挑选三个数字，如果这三个数字满足严格递增或者严格递减，则可以组成一个队伍。
问可以组成多少了队伍。

思路：数据量只有200，直接三层循环即可。

优化：预处理后可以两次循环计算出答案。

先使用两层循环预处理出每个数字两边严格大于与小于这个数字的个数。
然后两次循环计算答案。

三、设计地铁系统

题意：给一个指令序列。

1、a1 乘客 b1 时间 c1 车站上车。
2、a2 乘客 b2 时间 c2 车站下车。
3、询问此时从 c1 车站到 c2 车站的平均时间。

题意很简单，但是就是看不懂啥意思，相当于需求不明确。

不过有一个单词directly是个突破口，大胆猜测需要计算的乘客必须是从c1 上车且c2下车。

那两个人同时上车与同时下车算一趟车还是两趟车呢？
题中没有说明，只能分两次来尝试了。

这道题出的非常不好，不想说啥了，你们看代码就知道了，几行搞定。

四、good字符串

题意：给两个长度相等的字符串s1和s2，以及一个匹配字符串 evil。
在s1 到 s2 的字典序中，有很多字符串，如果某个字符串不存在 evil 子串，则成为 goog 字符串。

假设给的 s1 是 ab，s2 是 ae，区间内的字典序字符串有 ab、ac、ad、ae。

思路：典型的DFA状态机题，也是高级的动态规划题。

先不考虑DFA这个专业术语，我们遇到这个题该如何做呢？

一般可以想到枚举法，即从高到低枚举所有的字符串，判断是否满足。

枚举的时候，会发现有很多重复项，可以合并。

比如假设起始字符串是bbbb，结束字符串是yyyy，evil字符串是cdc。

那对于第一个位置，我们可以枚举a~z。
其中枚举分六中情况。

1、a在起始边界之外，非法
2、b在起始边界上，枚举有限制
3、c在evil上，枚举可能不是答案
4、d~x在内部，没有任意限制
5、y在结束边界上，枚举有限制
6、z在结束边界之外，非法

情况1和情况6最简单，直接结束枚举，没有答案。
情况4由于在内部，与evil无关，下一个位置可以任意枚举。
情况3比较特殊，如果下一个位置枚举的是d和c，则可能匹配evil，其他值则没有限制。
情况2和情况5只能枚举边界内，且需要考虑evil。

是不是很复杂？
我们暂时抽象一下这个问题。

做这种题有两种思路，一种是像上面那样直接分析区间内的所有情况，另一种是构造一个起始节点到目标节点的答案，通过求差找到。

这句话使用数学公式来表示大家就知道啥意思了。
假设我们要求的答案是 f(from, to)。
一种方法是直接构造出f(from, to)的状态机。
一种是构造一个F(0, num)的状态机，则可以推出f(from,to) = F(0, to) - F(0, form-1)。

前方高能，看不懂的建议直接看代码，代码更清晰一下。

当然，这两种状态机本质上没有区别的，只是后一种的状态机更为简单一些。

比如假设边界字符串czzz，evil字符串是cdc。
这时候情况就变成四种了。

1、枚举值任意选。
2、枚举值在 evil上。
3、枚举值在边界上。
4、枚举值在边界外。

当然，情况1与情况2可能有交集，这个我们暂时不需要考虑。

这里重点关注情况2，如果某次枚举不匹配，状态该如何转移呢？
我们会发现这个是典型的 KMP 匹配，需要构造 evil 的 next 函数。

有了KMP 的 next 函数，所有状态就都可以完美的跳转了。

由于 DFA 简单两句话介绍不清楚，大家可以看看代码，纸上画画，模拟几遍，应该就可以看懂了。

五、最后

这次比赛题目的难度分布太不均匀了， 前三题敲得快的话几分钟就做完了，而最后一题大部分则做不出来。

另外第三题题目描述有很大的问题，如果你没做出来，或者用了很长的时间，不是你的问题，是题目描述的有问题。

对DFA动态规划题该兴趣的同学，可以后台回复“ACM模板”获取我六年前整理的算法模板。

《完》

-EOF-

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