leetcode 第 380 场算法比赛

零、背景

这个周末有点事情，周六睡的非常晚，比赛就随便打了下。
第三题使用数位DP做，公式写复杂了，比赛期间没做出来。

A: 统计频率，选最大频率以及出现的次数。
B: 预处理 B 字符串出现的位置集合，再判断 A 出现的位置是否是答案。
C: 规律题，根据规律直接推导答案或者二分查找答案。
D: 与第二题一样，使用KMP或者hash计算子串出现的位置。

一、最大频率元素计数

题意：给一个数组，问所有具有最大频率的元素的总频率。

思路：预处理统计，然后扫描计算出现的最大频率以及个数，相乘就是总频率。

二、找出数组中的美丽下标 I

题意：給三个字符串 S、A、B，问 S 中子串为 A 起始下标满足要求的个数。
要求：A 的起始下标与某个子串为 B 的起始下标距离不大于 K。

思路：预处理计算所有的 B 子串下标。
对于每个子串 A， 在 B 的下标集合里二分查找最近的下标，判断距离。

小技巧：距离有两个，可以二分查找第一个大于的，减一就是最后一个小于等于的。

三、价值和小于等于 K 的最大数字

题意：给一个整数 k 和 x， 求一个数字 num，使得 1 到 num 所有数字的特殊1的个数之和小于等于 k。
特殊1定义：一个数字的二进制bit是 x 的倍数，且那一位为1，则个数加1。

思路：先分析二进制的规律，发现以 x 位为整体，可以从右上角特殊矩阵在不断嵌套扩大。

针对这个规律，有两种方案来解决这个问题。

方法1：按列处理。

如果我们可以快速一个 1到num 的特殊1个数之和，就可以通过二分查找来找到 num。

按列比特位来分别判断 x 位、2x位、3x位直到无穷大位出现 1 的个数，求和接口。

对于具体某一位 X 特殊1的个数，也是有规律的。
即每 2^X 个数字，出现 2^X/2 个 1。
解释：这些数字分为两半，前一半高位都是 0， 后一半高位都是 1，故出现个数是一半个。

所有对于 num， 统计有多少个 2^X 即可将完整的区域都计算。
对于的预期，可以判断是否超过一半来处理，没超过个数就是 0 个；超过时，超过多少个，就有多少 1。

方案2：数位DP。

数位 DP 比较复杂，文字不好介绍清楚，这里就不展开介绍了。

四、找出数组中的美丽下标 II

题意：与第二题一样。

思路：数据范围很大，不能枚举查找子串，需要进行优化。

方法1：hash 加速。

通过 hash 快速枚举找到所有子串，之后就与第二题没区别了。

PS：上个月在《字符串 hash》介绍过字符串 hash，套模板即可。

方法2：通过 kmp 快速找到子串，之后就与第二题没区别了。

五、最后

对于较复杂的算法或数据结构，使用纯文字很难介绍清楚。

在想要不要增加增加一个视频来辅助讲解这些算法。

《完》

-EOF-

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