上周的双周赛~
还是 3 题选手,这次周赛的题好像也简单了一点...
2299. Strong Password Checker II
Analysis
思路很直接,判断字符串是否符合要求即可。
Code
这是当时提交通过的代码:
1 | class Solution { |
可惜的是,一开始用的是if-else if
导致 WA 了一次。其实只要将是否出现连续字符单独拿出来判断就可以了。
实际上也可以用二进制位来取代bool
变量:
1 | class Solution { |
这种技巧会被用在状态压缩等其他高级解法中。
2300. Successful Pairs of Spells and Potions
Analysis
简单来讲,这个题就是在算笛卡尔积,然后统计对应的符合条件的结果即可。如果直接暴力,复杂度是 ,数量级在 ,肯定会超时。为了避免超时,就不能直接算笛卡尔积,可以先对 pairs 进行排序,然后遍历 spells 时,二分查找 pairs 中第一个满足条件的解,这样就可以直接得到符合条件的组合数目了。
Code
这是当时提交通过的代码:
1 | class Solution { |
这个题一开始也 WA 了一次,原因是 tmp 用的int
,没有考虑到 spells 中的数为 1,而 success 为超出int
范围的情况。实际上,当时比赛的时候,其实一看到 WA 就反应过来是 tmp 没用long long
的问题。而且,出错的那个用例正好是很长的那个,一看就知道是最后专门用来卡边界的。但是,自己还是死死的盯着输出和预期结果很久,浪费了不少时间😐。
实际上,上面的这段代码是向上取整的思路。对于正整数而言, 等价于 ,也等价于 。
那么,上面的代码可以改成:
1 | class Solution { |
2302. Count Subarrays With Score Less Than K
Analysis
这是第四个题,但是第三个提交的题。为什么第三个提交呢?因为差不多是原题...😂
类似的题是:713. Subarray Product Less Than K。
所以这个题的解法也很多,当时的思路是滑动窗口 + 前缀和的思路。
Code
这是当时提交通过的代码:
1 | class Solution { |
与其说是前缀和的思路,倒不如说是在模拟,不过也相差无几。