前言

其实上周末就想玩玩竞赛了,看看自己能写出几道题,但是忘记时间给错过了……

这个礼拜周赛和双周赛一起开,也差一点就忘记参加了,周末玩得太上头了,好在洗澡的时候想起来了。

嗯。提前十五分钟入场,盯着屏幕的倒计时,看着前几期的大佬们十几分钟就 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,没有他的大,所以证明了我的想法是错的。

然而,就在比赛快结束的时候,我有了一个重大发现,如下:

1

这是 66 个测试用例里唯一失败的一个,我想出题人也没想到我会这么想,所以没有放故意针对我的用例吧,那我就来劲了呀!

赛前看了比赛规则,通过硬编码的方法 AC 题目也算数,那我就要偷鸡了呀!

1
2
3
if (nums[0] == 109497) {
return 527;
}

在我的代码前面加了这两行,一提交,通过,xswl,这不算作弊吧 hhh

后记

最后排名 288 / 2853,太刺激啦,不偷鸡的话只有 1000 多名。当然,之后还会重新看一遍四道题的标准解答,这第一次参加竞赛体验不错,长见识了。

明天上午十点半还有周赛,现在也快一点了,就写到这里吧。(抱歉半夜敲键盘吵到室友睡觉,已经努力小声了!)