leetcode 第 361 场算法比赛

作者: | 更新日期:

RMQ 算法,用着太爽了。

本文首发于公众号:天空的代码世界,微信号:tiankonguse

零、背景

这次比赛第三题卡主了,导致排名不好。

其中第四题是 RMQ 算法的模板题,我整理了一个模板,感兴趣的可以参考下面的模板。

模板: https://github.com/tiankonguse/leetcode-solutions/blob/master/doc/lca.cpp

模板当前要求图 g 是有根树,如果 g 是无根树,特殊判断一下父节点即可。

一、统计对称整数的数目

题意:求指定范围内对称整数的数目。
对称整数:整数可以划分为前后相等长度的两半,每一半各位求和后相等。

思路:遍历范围所有数据,判断是不是对称整数。
判断:转字符串,求前一半的和与后一半的和,进行比较。
复杂度:O(n log(n))

优化:预处理出 [0,99]的各位之和。
然后根据数字的位数,快速得到两半的和。
复杂度:O(n)

二、生成特殊数字的最少操作

题意:给一个整数,问最少删除多少个数字,可以使得整数整除25。

思路:可以整除 25 的数字有 0 和 [25, 50, 75, 00] 为后缀的整数。

所以预处理每个数字出现的下标,然后看输入整数是否包含这些数字,以及顺序是否满足要求。

情况1:所有数字都删除,是一个答案。
情况2:如果存在 0,其他都删除则是一个答案。
情况3:判断是否存在满足前后顺序的两个数字。
具体来说,先判断个位是否存在。
存在了得到下标,再在十位判断是否存在大于个位下标的数字。
存在了,得到一个答案。

三、统计趣味子数组的数目

题意:给一个数组,以及模数 modulo 和余数 k。
问有多少个子数组,各数字对 modulo 取余后值是 k 的个数 再对 modulo 取余也是 k。

思路:题目有带你绕。

可以理解一个子数组是否满足要求。
假设子数组区间内余数等于 k 的个数有 cnt 个,要求 cnt 的约数等于 k。

第一步预处理找到所有余数等于 k 的下标。
第二步:选择若干下标区间,使得下标个数的余数为 k。

有多少个这样的区间呢?
可以发现以任何位置开始,选择前 k 个下标,肯定满足。再选择前k+mod个也满足,直到结尾。
复杂度:O(n * (n/mod))

1: k,k+mod,k+2mod,k+3mod+...
2: k+1, k+1+2mod,k+1+3mod+...
...

分析一下枚举情况,可以发现每隔mod行,就会有大量的重复项。
所以这些重复的,可以合并同类项,一起计算统计。
复杂度:O(mod * (n/mod))

1     : k,k+mod,k+2mod,k+3mod+...
1+ mod:   k+mod,k+2mod,k+3mod+...
1+2mod:         k+2mod,k+3mod+...

具体如何统计呢?
先看第一个位置的所有答案。

这里先下一个定义:原输入数组,余数不等于 k 的下标称为无效数字。
一个下标之前无效数字个数称为 pre[i]
一个下标之后无效数字个数称为 next[i]

选择前 pos[1,k] 下标区间时,答案是 (pre[1] + 1) * (next[k] + 1)
选择前 pos[1,k+mod] 下标区间是,答案是 (pre[1] + 1) * (next[k+mod] + 1)
选择前 pos[1,k+2mod] 下标区间是,答案是 (pre[1] + 1) * (next[k+2mod] + 1)

选择前 pos[mod+1,k+mod]下标区间时,答案是 (pre[mod+1] + 1) * (next[k+mod] + 1)
选择前 pos[2mod+1,k+2mod]下标区间时,答案是 (pre[2mod+1] + 1) * (next[k+2mod] + 1)
依次递推。

可以看到,遍历到k+j*mod时,公式右边都需要乘以 next[k+2mod] + 1
所以在枚举所有j*mod 时,公式左边可以累加起来,这样乘一次就可以了。

注意事项1:k 等于 0 时,连续的无效数字形成的子数组也可以选择。
注意事项2:如果整个数组没有有效下标,需要特殊处理。

代码: https://github.com/tiankonguse/leetcode-solutions/blob/master/contest/3/361/C.cpp

四、边权重均等查询

题意:给一个无根树,每个边有个不大于 26 的权值。
现在问任何两点的路径上,最少修改几个边,可以使得所有边都相等。

思路:问最少修改几个边,其实就是问路径上边权值出现次数最多的几条边。

看完这道题,最突出的数字就是权值值不大于 26,所以答案的突破口就在 26 这里。

无根树转化为有根树,即可预处理每个顶点到根节点路径上每个权值值出现的次数 W

然后通过 LCA(a,b) 找到两个询问顶点的最近公共祖先 c
两个顶点到权值统计次数都减去公共祖先的权值次数,即可得到两半路径的权值统计信息。
然后相加,即可得到路径的统计信息。

代码: https://github.com/tiankonguse/leetcode-solutions/blob/master/contest/3/361/D.cpp

五、最后

这次比赛第三题比较复杂,边界也比较多。
第四题想到权值统计后,就是跑 LCA 即可。
我这边求 LCA 都是使用 RMQ 来做的,模板也分享给大家。

模板: https://github.com/tiankonguse/leetcode-solutions/blob/master/doc/lca.cpp

《完》

-EOF-

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

本文首发于公众号:天空的代码世界,微信号:tiankonguse
如果你想留言,可以在微信里面关注公众号进行留言。

关注公众号,接收最新消息

tiankonguse +
穿越