leetcode 第 356 场算法比赛

零、背景

这次比赛最后一题我处理边界问题，浪费了很多时间。
昨晚四道题后，排名比较靠后了。

一、满足目标工作时长的员工数目

题意：给一个数组，问大于等于指定数字的个数。

思路：循环判断比大小统计即可。

二、统计完全子数组的数目

题意：给一个数组，集合大小为 S，问子数组中集合大小也为 S 的子数组个数。

思路1：枚举。
预先计算出集合大小 S。
枚举所有起始位置，找到集合大小为 S 的第一个前缀的右下标 R ，则[R,N]的都满足要求。
复杂度：O(n^2)

思路2：双指针。
预先计算出集合大小 S。
记录上个起始位置找到集合 S 时的信息(右下标 R 和集合)，下个起始位置找到集合大小为 S时，右下标肯定不会小于 R，所以可以在之前的信息上继续扫描。
复杂度：O(n)

三、包含三个字符串的最短字符串

题意：给三个字符串，求一个目标字符串使得三个字符串都是这个目标字符串的子串，且目标字符串长度最短。
如果有多个相同长度的，返回字典序最小的。

思路：两个字符串如果没有子串包含关系，则肯定是一个的后缀与另外一个的前缀相等，这样拼接出来的字符串才会最短。
假设一个字符串在前，一个在后，枚举所有前缀，最长的匹配的前缀就是最优答案。

只有3个字符串，枚举所有顺序A(3,3)中，得到的所有答案中选择最优答案即可。

四、统计范围内的步进数字数目

题意：问两个大整数[a,b]之间步进数字个数。
步进数字：数字相邻位差值的绝对值为1。

思路：数位 DP。

分为四部分判断：

1）a与b高位相等,只需要判断是否满足相邻数字差值是否满足要求。
2）a与b高位不等时拆分为三部分：低位、中间任意值、高位。
3）低位拆分为两部分：低位、中间任意值。 4）高位拆分为两部分：中间任意值、高位。
5）中间任意值：根据下个字母与剩余的长度，可以动态规划f(c,p)计算答案。

状态f(c,p)定义：前p个数字为任意值，下个值为c的答案个数。
方程:f(c,p) = f(c-1,p-1) + f(c+1,p-1)

注意事项：低位时，需要特殊处理前缀 0.

五、最后

这次比赛第三题你是怎么做的？有没有更简单的方法？

《完》

-EOF-

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