leetcode 第 342 场算法比赛

作者: | 更新日期:

周日上班,没参加比赛。

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

零、背景

周日要上班,所以就没参加周赛。

这几天工作上在忙项目评审的事情,没有时间写题解,项目评审之后,有时间了。
晚上做了一下题,分享下题解。

PS:分享了这么多算法比赛了,不知道大家有什么算法方面的诉求,如果有诉求,我可以出一些算法专题来提高大家的算法水平。

一、计算列车到站时间

题意:告诉列车预计出发时间与延迟时间,问实际出发时间。

思路:相加取模,一行代码搞定。

二、倍数求和

题意:问 n 以内能整除 3/5/7 的所有数字之和。

思路:循环判断是否可以整除,满足的相加即可。

三、滑动子数组的美丽值

题意:给一个数组,问长度为 k 的子数组中的第 x 小元素的值。

私聊:分析数据范围,数组大小为 10^5,数组的值大小为 [-50,50]

值统计,滑动窗口维护子数组中每个值出现的个数,暴力查询第 x 小的值。

复杂度:O(50 n)

四、使数组所有元素变成 1 的最少操作次数

题意:给一个数组,每次操作可以选择相邻的两个数字,其中一个的值可以设置为两个数字的最大公约数。
问最少几次操作,可以使得整个数组的值都是 1。

思路:贪心。

条件1:如果整个数组的最大公约数大于 1,则没有答案,否则肯定存在答案。

证明:假设某个子数组可以得到 1,则说明这个子数组通过若干次求最大公约数,得到了 1。
多个数字的最大公约数满足交换律,所以自数字的最大公约数必然是 1。
即整个数组的最大公约数是 1,与原始条件矛盾,所以假设不成立。

条件2:看数组中有没有值为 1 的数字,有的话,通过 1 就可以把其他数字都设置为 1。
答案为 数组大小减去 1 的个数。

证明:不管如何操作,每次只能设置一个值,即最有情况只能把一个非 1 的数字设置为 1。
所以总体最优情况是需要非 1 的个数。

条件3:先找到最短的最大公约数为 1 的子数组,假设长度是 len。
则答案为 n + len - 1

证明:所有数组刚开始都不是 1,当第一个 1 出现之后,根据条件2 可以证明,答案是数组大小减去 1 的个数,即第一个 1 出现之后,还需要 n-1次就可以得到答案。

所以,在第一个 1 出现之前,我们需要使用最少的次数,使得某个位置出现 1。

假设最短的最大公约数为 1 的子数组长度为 len,则需要 len-1次才能得到一个 1。
由条件1 可以证明,对于小于 len-1的子数组,都不能得到 1。

两个结合起来,答案就是 n + len - 1

怎么求最短的 gcd 为 1 的子数组呢?
数据范围只有 50,两层循环暴力计算即可。

五、最后

这次比赛比较简单。

大家可以思考下最后一题 n 很大时,该怎么做呢?
即怎么更快的找到最短的 gcd 为 1 的子数组长度。

小提示:利用单调性和公约数去重,即可在 log(V)时间和空间内求出某个位置为后缀的最短子数组。

《完》

-EOF-

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

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

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

tiankonguse +
穿越