leetcode 第 417 场算法比赛

零、背景

这次比赛题目不难，但是我失误较多，比如排名靠后了。

A: 模拟。
B: 暴力枚举。
C: 滑动窗口。
D: 递推。

排名：137
代码地址： https://github.com/tiankonguse/leetcode-solutions/tree/master/contest/4/417

一、找出第 K 个字符 I

题意：原始字符串长度为1，每次操作将字符串的所有字符加一后追加到原始字符串上。
求当字符串长度不小于k时，第 k 个字符是多少。

思路：标准做法是递推，不过这里数据里比较少，可以按题意模拟构造出字符串，然后输出第k个位置的答案。

二、元音辅音字符串计数 I

题意：给一个字符串，求所有包含5个元音字母且辅音个数恰好是 k 个子字符串个数。

思路：标准做法是滑动窗口，不过这里数据里较少，可以暴力枚举子字符串判断是否满足要求。

三、元音辅音字符串计数 II

题意：给一个字符串，求所有包含5个元音字母且辅音个数恰好是 k 个子字符串个数。

思路：与第二题一样，不过数据范围变大，需要使用滑动窗口来做。

预处理：预处理出每个前缀的辅音个数posToNum以及所有辅音个数首次出现的位置numToPos。
所有辅音个数首次出现位置的含义是，第1次出现的位置，第2次出现的位置等等。

滑动窗口：确定左边界 l，先找到包含5个元音的第一个右边界 r。
上面这个边界信息[l,r)是可以使用滑动窗口来供下个左边界使用的。

元音的边界确定后，需要下面四步来找到答案的左右边界。

1、通过a=posToNum[l-1]得知上个位置的辅音个数。
2、通过 L=numToPos[a+k] 来找到第一个满足 k 个辅音的左边界。
3、通过 R=numToPos[a+k+1]-1 来找到最后一个满足 k 个辅音的右边界。
4、答案就是 [l,r) 与 [l,R]的交集。

注意实现：辅音的边界可能不存在，建议先通过整个后缀来判断是否存在边界来剪枝。

四、找出第 K 个字符 I

题意：原始字符串长度为1，有两个操作。
操作1：将字符串保持不变追加到原始字符串上。
操作2：将字符串的所有字符加一后追加到原始字符串上。
告诉你操作列表，问当字符串长度不小于k时，第 k 个字符是多少。

思路：逆向递推。

假设当前求第 kn 个字符的答案，先计算出此时，字符串的长度 N 和操作次数 n。
应该满足这个关系：N/2 < kn <= N，即 kn 在字符串的右半部。

首先需要递归求出第 kn-N/2个字符的答案。

如果第 n 次是复制保持不变，则第 kn 个字符与第 k-N/2 个字符的值相等。
如果第 n 次复制时加1，则第 k 个字符为第k-N/2个字符的值加1。

代码实现的时候，如果使用代码递归，就简单一些。
如果使用循环递推，则需要累计加一的次数，最终根据加一的次数，计算出答案。

五、最后

这次比赛其实算两道题，一道滑动窗口，一道递推，还都不错的，适合用来当做面试题。

《完》

-EOF-

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