leetcode 第 302 场算法比赛 排名 144/6914

零、背景

手速还是不够快，犹豫一下，排名就到一百名之外了。

一、数组能形成多少数对

题意：给一个数组，每次可以删除一对相等的数字，问删除次数与最后剩余的数字个数。

思路：排序并统计每个数字出现次数即可求出答案。

二、数位和相等数对的最大和

题意：给一个数组，数位和相等的两个数字可以形成一组匹配，求数字和最大的一个匹配。

思路：循环数组，map 记录之前每个数位和中最大的数字，求和更新答案即可。

三、裁剪数字后查询第 K 小的数字

题意：给一个等长的数字字符串数组，然后给若干询问。
每个询问有两个数字[k, trim]。
trim 代表对字符串的后缀长度。
求后缀按字典序排名为 k 的下标（字符串相等时按下标大小比较）。

思路：储存字符串的下标，每个询问时对下标按题目要求排序，输出第 k 个即可。
复杂度：O(Q * N * log(N) * L)
Q 代表询问个数。
N 代表字符串个数。
L 代表字符串的长度，需要进行字典序比较。

四、使数组可以被整除的最少删除次数

题意：给两个数组，第一个数组可以从小到大删除数字。
问删除多少个数字，才能使得第一个数字的最小值可以整除第二个数组的所有数字。

思路：要整除第二个数组的所有数字，代表这个数字是第二个数组所有数字的公约数。
所以可以先预处理求出第二个数组的最大公约数。
然后对第一个数组排序，从小到大找到第一个可以整除的数字即可。

最大公约数复杂度：O(n log(n))
排序复杂度：O(n log(n))
寻找复杂度：O(n)
综合复杂度：n log(n)

五、最后

这次比赛题目很简单，可能是考察排序吧。

加油，算法人。

《完》

-EOF-

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