leetcode 第 281 场算法比赛

零、背景

这次比赛的时候，leetcode 中文网站 502 了，预计比赛成绩会不算数吧。

一、统计各位数字之和为偶数的整数个数

题意：给一个数字 n, 求小于等于 n 的正整数里面，各位数字之和为偶数的正整数个数。

思路：按照题意循环一次判断即可。

笔误：求各位之和时，不知怎么想的，除2模2了，求得是二进制各位之和。

二、合并零之间的节点

题意：给一个链表，对于中间非 0 的连续节点，进行求和合并。
最后删除所有值为 0 的节点，按顺序返回链表。

思路：题目保证收尾都有一个 0 节点，那无脑循环合并并删除 0 节点即可。

三、构造限制重复的字符串

题意：给一个字符串，可以打乱重排列（允许删除字符），要求返回字典序最大字符串，但连续字符不能超过指定限制。

思路：字典序最大，字母值最大的需要优先放在最前面。

所以可以贪心优先选择值最大的字母，到达限制后，放一个次大的字母，之后接着放最大的字母。
按照这个规则直到只剩一个字母即可。

最后一个字母触发最大限制后，由于没有次大字母，剩余的字母就是都需要删除的字母。

笔误：计数变量把类型写成 char 一字节了，导致答案错误一次。

四、统计可以被 K 整除的下标对数目

题意：给一个数组，问任意两个数字组合相乘，可以整除 k 的个数。

思路：数据范围很大，暴力做理论上会超时。

由于是求是否可以整除 k ，与 K 约数无关的值可以忽略。
所以我们只需要预处理数组，分别求出数组与 k 的最大公共部分，即最大公约数。

这样，数组就按最大公约数进行了分组。

可以推导：
K 的质数约数最多有log(k) 个
K 的约数个数则最多有 2^log(k)=k 个。

由于相同质数约数会使约数个数快速减少，比如全是 2 时，最大是2^17 ，约数个数也只有 1+17=18 个。

另外，约数越大时，质数约数的个数也会快速收敛，比如质数都不同时，最大是2*3*5*7*11*13*17 ，约数个数只有2^7 个。

最坏情况下，约数的个数也不会超过 2*sqrt(k) 。
所以，数组分组后不会超时，复杂度 4*k 。

精确的复杂度无法给出，网上也没找到。
​但是找到一个复杂度上限，见下图。

分组再进行两两组合，就可以求出答案。
综合复杂度 4*k

注意事项：由于进行了分组，分组内也需要判断是否可以组合整除 K。

笔误：分组内组合的时候，由于公约数相等，我就没有相乘，错误一次。

PS：想到原先复杂度比较复杂后，去研究了其他人的代码，发现大多都是使用筛法解决的。

正解：假设数组中的值是 v，与 k 的公约数是 gcd(v,k)。
则需要统计出数组中可以整除 k/gcd(v,k)的数字个数，这次都可以组成答案。

通过筛法，就可以预处理出每个数字的倍数（进一步优化是只求 k 的公约数的倍数）
复杂度： n + n/2 + n/3 + n/4 + ...

然后循环计算出所有组合，再减去重复计算的组合，就可以求出答案了。

五、最后

这次比赛比较简单，但是我最后两题分别错误一次，不然应该可以进前百名吧。

加油，算法人。

《完》

-EOF-

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