第一次参加 LeetCode 竞赛有感。
前言
其实上周末就想玩玩竞赛了,看看自己能写出几道题,但是忘记时间给错过了……
这个礼拜周赛和双周赛一起开,也差一点就忘记参加了,周末玩得太上头了,好在洗澡的时候想起来了。
嗯。提前十五分钟入场,盯着屏幕的倒计时,看着前几期的大佬们十几分钟就 AC 了四道题,我内心忐忑。
第一题
给你一个混合字符串 s ,请你返回 s 中 第二大 的数字,如果不存在第二大的数字,请你返回 -1 。
混合字符串 由小写英文字母和数字组成。
作为热身题当然是一道简单题,我的思路是遍历一遍字符串,把数字筛选出来放到 HashSet
里,然后再转到 ArrayList
里调用 sort()
排序,返回出第二大的值,之所以不自己写排序的原因是想节省时间。
然而由于自己对于 sort()
函数的不熟悉,导致搞不对语法好久,甚至还百度了函数的用法。不过还算顺利,15 分钟完成 AC。但是我刚出来准备去写下一题的时候,瞟了一眼排行榜,发现第一的大佬 12 分钟的时候就全部完成四道题了,HP-1。不慌,我写好自己的就行了,下一题。
第二题
你需要设计一个包含验证码的验证系统。每一次验证中,用户会收到一个新的验证码,这个验证码在
currentTime
时刻之后timeToLive
秒过期。如果验证码被更新了,那么它会在currentTime
(可能与之前的currentTime
不同)时刻延长timeToLive
秒。
请你实现AuthenticationManager
类:
AuthenticationManager(int timeToLive)
构造AuthenticationManager
并设置timeToLive
参数。generate(string tokenId, int currentTime)
给定tokenId
,在当前时间currentTime
生成一个新的验证码。renew(string tokenId, int currentTime)
将给定tokenId
且 未过期 的验证码在currentTime
时刻更新。如果给定tokenId
对应的验证码不存在或已过期,请你忽略该操作,不会有任何更新操作发生。countUnexpiredTokens(int currentTime)
请返回在给定currentTime
时刻,未过期 的验证码数目。
如果一个验证码在时刻t
过期,且另一个操作恰好在时刻t
发生(renew
或者countUnexpiredTokens
操作),过期事件优先于其他操作。
看到题目我就懵了呀,从来没见过这么长的题目,但当我写完之后才发现,这都是吓人的,就像数学题一样,字越多越简单。
然而我看题目,理解题目就花了好多时间,写代码,Debug 又花了好多时间,虽然代码量一点都不大,并且也是一次就 AC,但写完这题我已经花了快五十多分钟了。
第三题
给你一个长度为
n
的整数数组coins
,它代表你拥有的n
个硬币。第i
个硬币的值为coins[i]
。如果你从这些硬币中选出一部分硬币,它们的和为x
,那么称,你可以 构造 出x
。
请返回从0
开始(包括0
),你最多能 构造 出多少个连续整数。
你可能有多个相同值的硬币。
乍一看,这应该是一道动态规划的题,并且我之前也做了不少动态规划。
仔细一想,哎,怎么一点思路都没有。
跳过,下一题,这题到最后都没写,之后会再研究研究。
第四题
给你
nums
,它是一个大小为2 * n
的正整数数组。你必须对这个数组执行n
次操作。
在第i
次操作时(操作编号从1
开始),你需要:
选择两个元素x
和y
。
获得分数i * gcd(x, y)
。
将x
和y
从nums
中删除。
请你返回n
次操作后你能获得的分数和最大为多少。
函数gcd(x, y)
是x
和y
的最大公约数。
困难题,我的思路(错的):因为题目说 1 <= n <= 7
,我就想遍历数组,找出最大的公因数,然后乘最大的系数,最后加起来。
然而我的思路是有问题的,我只考虑了当前最大的公因数,没考虑综合结果是否是最大的,最后结果也证明了,有一个测试用例预期输出是 527
,我的输出是 525
,没有他的大,所以证明了我的想法是错的。
然而,就在比赛快结束的时候,我有了一个重大发现,如下:
这是 66 个测试用例里唯一失败的一个,我想出题人也没想到我会这么想,所以没有放故意针对我的用例吧,那我就来劲了呀!
赛前看了比赛规则,通过硬编码的方法 AC 题目也算数,那我就要偷鸡了呀!
1 | if (nums[0] == 109497) { |
在我的代码前面加了这两行,一提交,通过,xswl,这不算作弊吧 hhh
后记
最后排名 288 / 2853,太刺激啦,不偷鸡的话只有 1000 多名。当然,之后还会重新看一遍四道题的标准解答,这第一次参加竞赛体验不错,长见识了。
明天上午十点半还有周赛,现在也快一点了,就写到这里吧。(抱歉半夜敲键盘吵到室友睡觉,已经努力小声了!)