leetcode 第 306 场算法比赛

零、背景

这次比赛最后一题有点难度，是数位 DP，可惜我也花费了不少时间。

一、矩阵中的局部最大值

题意：给一个 n*n 的矩阵，求一个 (n-2)*(n-2) 的矩阵，矩阵的值是上下左右 9 个方格的最大值。

思路：按照题意四层循环求最值即可。

复杂度：O(3^2 * n^2)

二、边积分最高的节点

题意：给一个有向图，每个节点都有一个出边。
每个节点的得分是所有入度节点编号之和。
求最大得分的编号，有相等得分时返回编号最小的那个。

思路：遍历所有边计算出每个节点的得分，再循环一遍求答案即可。

注意事项：得分可能大于 32 位最大值，需要使用 64 位整数。

三、根据模式串构造最小数字

题意：给一个长度为 n 的只包含I和D的字符串，I代表相邻两个数字是大于关系，D是小于关系。
求构造一个长度为 n+1 的数组，使得相邻数字的关系满足输入字符串的规则。

思路：本想使用动态规划来做这道题。
但是考虑到这是第三题，显然不需要这么复杂。

心中大概计算了下，排列组合共有9! 中情况，但是在输入规则的限制下，数据量会快速衰减，搜索不会超时。
于是我便暴力搜索来做了。

不完备的大致推导：

对于相邻两个数字，不是大于就是小于，共有A(n, 2)中情况。
但是确定了大小关系，满足要求的情况就是 C(n, 2)个了。

规则每多一位，数据量就减半，所以大概满足要求的答案个数是 A(n)/2^n个。

再加上是求满足规则的字典序最小的那个，枚举会很快遇到答案，之后就不需要枚举了，所以速度会更快。

四、统计特殊整数

题意：如果一个整数里面各位的数字都不同，则称为特殊数。
求[1, n]区间内，特殊数的个数。

思路：典型的数位动态规划，一个 DFS 搞定。

数位动态规划万能模板如下。

假设询问的 n 长度为 L, 最高位数字为 k，则答案分三种情况。

首先答案分两种情况：

第一种情况：[1,10^L] 的数字，最高位不能有前导零，之后可以有 0。
答案固定，直接推导公式计算即可。

第二种情况： 数字为 k 位且与 n 有相同前缀的。
由于位数为 L，所有共有 L 中相同前缀。
从最高位到最低位，枚举处理每一个前缀的情况。

前缀固定后，假设前缀是 k0 k1 ... ka，剩余的长度为 len。
使得 k0 k1 ... ka-1 固定，枚举 ka 这一位，枚举值为 [1, ka-1]。
枚举之后，剩余的位数任意选择，求满足规则的个数。

复杂度：O(n * L)

五、最后

这次比赛会卡不少人。
第二题会有人遇到越界的问题，比如我就遇到了。
第三题会有人不敢暴力搜索，动态规划有太复杂，会浪费不少时间。
第四题经典的数位DP，属于高级动态规划，也会卡主一些人。

这样看来，这次比赛的质量还算可以，不过我也被卡主了。

加油，算法人。

《完》

-EOF-

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