上周末的第 305 场周赛遭遇滑铁卢，比赛期间四道题目只做出了两道题。主要原因就是在第三题“坐牢”了——纠结了很久，到比赛最后还没做出来，导致第四题都没怎么认真看。最后看到第四题还只是中等难度的时候已经来不及做了…… 今天来复盘一下这次周赛“坐牢”的原因，希望以后注意改正。

1 背景

上上周的第 304 场周赛在比赛的时候 AK 了，但是赛后补的测试用例最后一题没过，所以成绩不是很好（2056 / 7372），竞赛分数掉了 7 分。

所以上周末就想着要上分补回来。周六白天加班，晚上是第 84 场双周赛，但状态还算正常，四道题全过，排名 573 / 4574（就是提交错了 4 次多加了 20 min 有点懊恼）。然后就有点飘了，打完双周赛就去玩《艾尔登法环》去了，熬夜到挺晚。

结果周日一觉睡到十点多，起床后赶紧把 IDE 开好，洗漱完直接开始周赛。感觉自己的比赛状态受这一点影响还是挺大的，这样昏昏沉沉状态对于力扣周赛这种拼速度的竞赛（相较于自己日常刷题可以懒懒散散慢慢想）来说就是大忌，这是日后必须要注意的一点——脑力劳动之前千万不要熬夜……

2 过程

2.1 第一题

开始比赛后，第一题就给自己埋下了坑。这里先复盘一下题目：

2367. 算术三元组的数目 难度：简单 给你一个下标从 0 开始、严格递增 的整数数组 和一个正整数 。如果满足下述全部条件，则三元组 就是一个 算术三元组 ： 返回不同 算术三元组 的数目。 示例 1： 示例 2： 提示： 来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/number-of-arithmetic-triplets 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

怎么样？你看了是否有思路呢？毕竟是简单题，而且有 不超过 200 个元素的限制，所以直接

复杂度的三重 for 循环，或者 scala 里面的 方法（表示所有 C(3, n) 的组合，返回是一个迭代器）都可以通过。我最终通过的代码如下（三重循环可以参考竞赛前几名的代码，大部分都是直接三重循环）：

def arithmeticTriplets(nums: Array[Int], diff: Int): Int = {
    nums.indices.combinations(3)
     .count(arr => nums(arr(1)) - nums(arr(0)) == diff && nums(arr(2)) - nums(arr(1)) == diff)
}

看题解可以知道，更加好的选择是使用哈希表一次遍历：对于每一个 的元素都先验证元素减 和减 是不是都在哈希表里，再无论如何把元素加到哈希表中。这样算法的时间复杂度就只有

了。这个思路很好理解，这里我就不贴代码了。

类似的，同等时间复杂度还有双指针一次遍历的方法：把哈希表换成两个指示减 和减 所在位置的指针即可。

然而我在比赛时，首先想到的就是三重循环的这种方法，但感觉时间复杂度太拉胯了，一时间又没有更好的思路，就先跳过了第一题，直接做第二题去了。这就为后来最终成绩很差埋下隐患：我们知道，力扣的单场比赛排名首先是按通过题目的总分来排，相等分数再按最后通过时间来排（当然还有错误提交罚 5 min）。等我第三题坐牢回来做第一题时，已经是一个小时后了，等于说排名是按一个小时去和只通过前两题的人排的……

所以，很重要的一点，能通过的题目一定要率先赶紧解决。不然遇上极端情况，回过头来补前面的题目的通过时间成为了最后通过耗时的话，那还是很吃亏的。 其次就是注意观察题目数据范围，有时不必过于纠结时间复杂度。有时候数据量小的话，暴力也是可以通过的。但是看着我第一题 7888 ms 的通过时间，感觉也是挺玄幻的。（不知道会不会也补案例变成不通过……）

2.2 第二题

第二题通过还是很顺利的，十三分钟的时候就已经提交通过了：

2368. 受限条件下可到达节点的数目 难度：中等 现有一棵由 个节点组成的无向树，节点编号从 到 ，共有 条边。 给你一个二维整数数组 ，长度为 ，其中 表示树中节点 和 之间存在一条边。另给你一个整数数组 表示 受限 节点。 在不访问受限节点的前提下，返回你可以从节点 0 到达的 最多 节点数目。 注意，节点 不 会标记为受限节点。 示例 1： 示例 2： 提示： 来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/reachable-nodes-with-restrictions 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路很简单，DFS + 数组作为已访问和受限的元素的哈希表，直接计数即可。代码如下（这里 DFS 的逻辑是使用队列迭代实现的，没有用递归）：

def reachableNodes(n: Int, edges: Array[Array[Int]], restricted: Array[Int]): Int = {
    val visit = new Array[Boolean](n)
    restricted.foreach(visit(_) = true)
    val map = edges.flatMap(arr => Array(arr(0) -> arr(1), arr(1) -> arr(0))).groupBy(_._1).mapValues(_.map(_._2))
    val q = new scala.collection.mutable.Queue[Int]
    q enqueue 0
    visit(0) = true
    var result = 1
    while (q.nonEmpty) {
        var size = q.size
        while (size > 0) {
            val i = q.dequeue()
            if (map.contains(i)) {
                for (to <- map(i) if !visit(to)) {
                    visit(to) = true
                    q.enqueue(to)
                    result += 1
                }
            }
            size -= 1
        }
    }
    result
}

2.3 第三题

这下到了我“坐牢”的第三题了。说实话事后看别人题解发现确实不难，但自己就是硬生生在这道题坐了一小时十五分钟的牢。

2369. 检查数组是否存在有效划分 难度：中等 给你一个下标从 0 开始的整数数组 ，你必须将数组划分为一个或多个 连续 子数组。 如果获得的这些子数组中每个都能满足下述条件 之一 ，则可以称其为数组的一种 有效 划分： 如果数组 至少 存在一种有效划分，返回 ，否则，返回 。 示例 1： 示例 2： 提示： 来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/check-if-there-is-a-valid-partition-for-the-array 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

让自己坐牢的思路是这样的：三种有效划分中显然最特别的是第三种——连续递增 1 的三个元素。中间的那个元素一定是单个的。那么我们可以把那些单个元素找出来，判断它们是否满足第三种情况。然后对于剩下的元素，我们看它们相同的元素是不是连续的即可（连续意味着 2 个以上，都可以拆分成任意个 2 或 3 的和）。

但是事实上，这样做就要面对很多边界情况：单个元素是可以和单个元素组成连续递增 1 的三个元素，也可以抽一个连续的元素来组成连续递增 1 的三个元素，然后被抽取过的连续元素，就需要判断是不是只剩下一个（这样就又不可以了）。在不断的提交和被边界条件判不通过的反复中，时间最终被耗尽了。

实际上看题解就知道，动态规划其实很快就可以解决：

def validPartition(nums: Array[Int]): Boolean = {
    val n = nums.length
    val dp = new Array[Boolean](n + 1)
    dp(0) = true
    var i = 0
    while (i < n) {
        if (dp(i)) {
            if (i + 1 < n && (nums(i) == nums(i + 1))) dp(i + 2) = true
            if (i + 2 < n && (nums(i) == nums(i + 1)) && (nums(i) == nums(i + 2))) dp(i + 3) = true
            if (i + 2 < n && (nums(i) + 1 == nums(i + 1)) && (nums(i) + 2 == nums(i + 2))) dp(i + 3) = true
        }
        i += 1
    }
    dp(n)
}

看状态转移能不能把 true 按照三种方式传递到最后即可。代码很简单，思路很清晰。但自己比赛的时候就是掉入了无穷无尽的细节里面爬不出来了，也一直没有重新跳出错误的思路，导致本次周赛坐牢，体验贼差。

所以，比赛过程中，如果发现自己的思路导致边界条件判断繁琐，无法有效解决题目时，就要及时重新审视自己的思路本身是否有问题。方向比努力更重要啊……

2.4 第四题

第四题在比赛时没来得及做，但是最后让我看到了只是中等难度（心脏骤停）。知道不难却没有时间做，难受啊……

2370. 最长理想子序列 难度：中等 给你一个由小写字母组成的字符串 ，和一个整数 。如果满足下述条件，则可以将字符串 视作是 理想字符串 ： 返回 最长 理想字符串的长度。 字符串的子序列同样是一个字符串，并且子序列还满足：可以经由其他字符串删除某些字符（也可以不删除）但不改变剩余字符的顺序得到。 注意：字母表顺序不会循环。例如， 和 在字母表中位次的绝对差值是 ，而不是 。 示例 1： 示例 2： 提示： 来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/longest-ideal-subsequence 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

因为考场上没做，这里就直接附比赛之后自己写的通过代码了：

def longestIdealString(s: String, k: Int): Int = {
    val f = new Array[Int](26)
    for (i <- s.indices) {
        val c = s.charAt(i) - 'a'
        for (j <- Math.max(c - k, 0) to Math.min(c + k, 25)) {
            f(c) = Math.max(f(c), f(j))
        }
        f(c) += 1
    }
    f.max
}

重点要想到把时间复杂度转嫁到固定的较小的数值上（本体是 26，即小写字符数量）—— 枚举字符，然后动态规划，其实还是有点难想的。这里就不细说了，主要还是总结周赛的失误。

最后一点，那就是前面的问题解决不了的时候，可以简单看看后面的题目。不过这一点就和第一题的行为起了冲突，当时就是解决不了第一题，就跳到后面看第二题了。所以我们需要加个限定：在后面题目有头绪时就做后面的试试看，不然就优先把难度低的题目解决完。

3 总结

总之，这次周赛怕是要掉很多分，以后要好好吸取这次的经验。最近也看了前几名的大佬们的代码，发现基本都是 C++ 居多。一方面当然有算法竞赛训练一般都是使用 C++ 的原因；另一方面我感觉是因为对于算法题来说，语言其实不重要，最重要的还是在于思路清晰。语法糖带来的帮助也许只是蝇头小利，前提还是自己想明白了怎么做。自己还是要多思考，多总结，多复盘，这样才有提高。

题外话：周赛“坐牢”让自己周日心情很差，本来打算写点代码或者文章的，结果下午和晚上基本都去打《艾尔登法环》了（捂脸）……