杂谈 - 力扣第 305 场周赛“坐牢”的问题复盘
上周末的第 305 场周赛遭遇滑铁卢，比赛期间四道题目只做出了两道题。主要原因就是在第三题“坐牢”了——纠结了很久，到比赛最后还没做出来，导致第四题都没怎么认真看。最后看到第四题还只是中等难度的时候已经来不及做了…… 今天来复盘一下这次周赛“坐牢”的原因，希望以后注意改正。
1 背景
上上周的第 304 场周赛在比赛的时候 AK 了，但是赛后补的测试用例最后一题没过，所以成绩不是很好（2056 / 7372），竞赛分数掉了 7 分。
所以上周末就想着要上分补回来。周六白天加班，晚上是第 84 场双周赛，但状态还算正常，四道题全过，排名 573 / 4574（就是提交错了 4 次多加了 20 min 有点懊恼）。然后就有点飘了，打完双周赛就去玩《艾尔登法环》去了，熬夜到挺晚。
结果周日一觉睡到十点多，起床后赶紧把 IDE 开好，洗漱完直接开始周赛。感觉自己的比赛状态受这一点影响还是挺大的，这样昏昏沉沉状态对于力扣周赛这种拼速度的竞赛（相较于自己日常刷题可以懒懒散散慢慢想）来说就是大忌，这是日后必须要注意的一点——脑力劳动之前千万不要熬夜……
2 过程
2.1 第一题
开始比赛后，第一题就给自己埋下了坑。这里先复盘一下题目：
2367. 算术三元组的数目 难度：简单
给你一个下标从 0 开始、严格递增 的整数数组
nums和一个正整数diff。如果满足下述全部条件，则三元组(i, j, k)就是一个 算术三元组 ：
i < j < k，
nums[j] - nums[i] == diff且
nums[k] - nums[j] == diff返回不同 算术三元组 的数目。
示例 1：
输入：nums = [0,1,4,6,7,10], diff = 3
输出：2
解释：
(1, 2, 4) 是算术三元组：7 - 4 == 3 且 4 - 1 == 3 。
(2, 4, 5) 是算术三元组：10 - 7 == 3 且 7 - 4 == 3 。示例 2：
输入：nums = [4,5,6,7,8,9], diff = 2
输出：2
解释：
(0, 2, 4) 是算术三元组：8 - 6 == 2 且 6 - 4 == 2 。
(1, 3, 5) 是算术三元组：9 - 7 == 2 且 7 - 5 == 2 。提示：
3 <= nums.length <= 200
0 <= nums[i] <= 200
1 <= diff <= 50
nums严格 递增来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/number-of-arithmetic-triplets 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
怎么样？你看了是否有思路呢？毕竟是简单题，而且有 nums 不超过 200 个元素的限制，所以直接
复杂度的三重 for 循环，或者 scala 里面的 combinations 方法（表示所有 C(3, n) 的组合，返回是一个迭代器）都可以通过。我最终通过的代码如下（三重循环可以参考竞赛前几名的代码，大部分都是直接三重循环）：
看题解可以知道，更加好的选择是使用哈希表一次遍历：对于每一个 nums 的元素都先验证元素减 diff 和减 2 * diff 是不是都在哈希表里，再无论如何把元素加到哈希表中。这样算法的时间复杂度就只有
了。这个思路很好理解，这里我就不贴代码了。
类似的，同等时间复杂度还有双指针一次遍历的方法：把哈希表换成两个指示减 diff 和减 2 * diff 所在位置的指针即可。
然而我在比赛时，首先想到的就是三重循环的这种方法，但感觉时间复杂度太拉胯了，一时间又没有更好的思路，就先跳过了第一题，直接做第二题去了。这就为后来最终成绩很差埋下隐患：我们知道，力扣的单场比赛排名首先是按通过题目的总分来排，相等分数再按最后通过时间来排（当然还有错误提交罚 5 min）。等我第三题坐牢回来做第一题时，已经是一个小时后了，等于说排名是按一个小时去和只通过前两题的人排的……
所以，很重要的一点，能通过的题目一定要率先赶紧解决。不然遇上极端情况，回过头来补前面的题目的通过时间成为了最后通过耗时的话，那还是很吃亏的。
其次就是注意观察题目数据范围，有时不必过于纠结时间复杂度。有时候数据量小的话，暴力也是可以通过的。但是看着我第一题 7888 ms 的通过时间，感觉也是挺玄幻的。（不知道会不会也补案例变成不通过……）
2.2 第二题
第二题通过还是很顺利的，十三分钟的时候就已经提交通过了：
2368. 受限条件下可到达节点的数目 难度：中等
现有一棵由
n个节点组成的无向树，节点编号从0到n - 1，共有n - 1条边。给你一个二维整数数组
edges，长度为n - 1，其中edges[i] = [ai, bi]表示树中节点ai和bi之间存在一条边。另给你一个整数数组restricted表示 受限 节点。在不访问受限节点的前提下，返回你可以从节点 0 到达的 最多 节点数目。
注意，节点
0不 会标记为受限节点。示例 1：
输入：n = 7, edges = [[0,1],[1,2],[3,1],[4,0],[0,5],[5,6]], restricted = [4,5]
输出：4
解释：在不访问受限节点的前提下，只有节点 [0,1,2,3] 可以从节点 0 到达。示例 2：
输入：n = 7, edges = [[0,1],[0,2],[0,5],[0,4],[3,2],[6,5]], restricted = [4,2,1]
输出：3
解释：在不访问受限节点的前提下，只有节点 [0,5,6] 可以从节点 0 到达。提示：
2 <= n <= 10^5
edges.length == n - 1
edges[i].length == 2
0 <= ai, bi < n
ai != bi
edges表示一棵有效的树
1 <= restricted.length < n
1 <= restricted[i] < n
restricted中的所有值 互不相同来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/reachable-nodes-with-restrictions 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路很简单，DFS + visit 数组作为已访问和受限的元素的哈希表，直接计数即可。代码如下（这里 DFS 的逻辑是使用队列迭代实现的，没有用递归）：
2.3 第三题
这下到了我“坐牢”的第三题了。说实话事后看别人题解发现确实不难，但自己就是硬生生在这道题坐了一小时十五分钟的牢。
2369. 检查数组是否存在有效划分 难度：中等
给你一个下标从 0 开始的整数数组
nums，你必须将数组划分为一个或多个 连续 子数组。如果获得的这些子数组中每个都能满足下述条件 之一 ，则可以称其为数组的一种 有效 划分：
子数组 恰 由
2个相等元素组成，例如，子数组[2,2]。子数组 恰 由
3个相等元素组成，例如，子数组[4,4,4]。子数组 恰 由
3个连续递增元素组成，并且相邻元素之间的差值为1。例如，子数组[3,4,5]，但是子数组[1,3,5]不符合要求。如果数组 至少 存在一种有效划分，返回
true，否则，返回false。示例 1：
输入：nums = [4,4,4,5,6]
输出：true
解释：数组可以划分成子数组 [4,4] 和 [4,5,6] 。
这是一种有效划分，所以返回 true 。示例 2：
输入：nums = [1,1,1,2]
输出：false
解释：该数组不存在有效划分。提示：
2 <= nums.length <= 10^5
1 <= nums[i] <= 10^6来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/check-if-there-is-a-valid-partition-for-the-array 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
让自己坐牢的思路是这样的：三种有效划分中显然最特别的是第三种——连续递增 1 的三个元素。中间的那个元素一定是单个的。那么我们可以把那些单个元素找出来，判断它们是否满足第三种情况。然后对于剩下的元素，我们看它们相同的元素是不是连续的即可（连续意味着 2 个以上，都可以拆分成任意个 2 或 3 的和）。
但是事实上，这样做就要面对很多边界情况：单个元素是可以和单个元素组成连续递增 1 的三个元素，也可以抽一个连续的元素来组成连续递增 1 的三个元素，然后被抽取过的连续元素，就需要判断是不是只剩下一个（这样就又不可以了）。在不断的提交和被边界条件判不通过的反复中，时间最终被耗尽了。
实际上看题解就知道，动态规划其实很快就可以解决：
看状态转移能不能把 true 按照三种方式传递到最后即可。代码很简单，思路很清晰。但自己比赛的时候就是掉入了无穷无尽的细节里面爬不出来了，也一直没有重新跳出错误的思路，导致本次周赛坐牢，体验贼差。
所以，比赛过程中，如果发现自己的思路导致边界条件判断繁琐，无法有效解决题目时，就要及时重新审视自己的思路本身是否有问题。方向比努力更重要啊……
2.4 第四题
第四题在比赛时没来得及做，但是最后让我看到了只是中等难度（心脏骤停）。知道不难却没有时间做，难受啊……
2370. 最长理想子序列 难度：中等
给你一个由小写字母组成的字符串
s，和一个整数k。如果满足下述条件，则可以将字符串t视作是 理想字符串 ：
t是字符串s的一个子序列。
t中每两个 相邻 字母在字母表中位次的绝对差值小于或等于k。返回 最长 理想字符串的长度。
字符串的子序列同样是一个字符串，并且子序列还满足：可以经由其他字符串删除某些字符（也可以不删除）但不改变剩余字符的顺序得到。
注意：字母表顺序不会循环。例如，
'a'和'z'在字母表中位次的绝对差值是25，而不是1。示例 1：
输入：s = "acfgbd", k = 2
输出：4
解释：最长理想字符串是 "acbd" 。该字符串长度为 4 ，所以返回 4 。
注意 "acfgbd" 不是理想字符串，因为 'c' 和 'f' 的字母表位次差值为 3 。示例 2：
输入：s = "abcd", k = 3
输出：4
解释：最长理想字符串是 "abcd" ，该字符串长度为 4 ，所以返回 4 。提示：
1 <= s.length <= 10^5
0 <= k <= 25
s由小写英文字母组成来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/longest-ideal-subsequence 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
因为考场上没做，这里就直接附比赛之后自己写的通过代码了：
重点要想到把时间复杂度转嫁到固定的较小的数值上（本体是 26，即小写字符数量）—— 枚举字符，然后动态规划，其实还是有点难想的。这里就不细说了，主要还是总结周赛的失误。
最后一点，那就是前面的问题解决不了的时候，可以简单看看后面的题目。不过这一点就和第一题的行为起了冲突，当时就是解决不了第一题，就跳到后面看第二题了。所以我们需要加个限定：在后面题目有头绪时就做后面的试试看，不然就优先把难度低的题目解决完。
3 总结
总之，这次周赛怕是要掉很多分，以后要好好吸取这次的经验。最近也看了前几名的大佬们的代码，发现基本都是 C++ 居多。一方面当然有算法竞赛训练一般都是使用 C++ 的原因；另一方面我感觉是因为对于算法题来说，语言其实不重要，最重要的还是在于思路清晰。语法糖带来的帮助也许只是蝇头小利，前提还是自己想明白了怎么做。自己还是要多思考，多总结，多复盘，这样才有提高。
题外话：周赛“坐牢”让自己周日心情很差，本来打算写点代码或者文章的，结果下午和晚上基本都去打《艾尔登法环》了（捂脸）……
