上周末的第 305 場(chǎng)周賽遭遇滑鐵盧，比賽期間四道題目只做出了兩道題。主要原因就是在第三題“坐牢”了——糾結(jié)了很久，到比賽最后還沒(méi)做出來(lái)，導(dǎo)致第四題都沒(méi)怎么認(rèn)真看。最后看到第四題還只是中等難度的時(shí)候已經(jīng)來(lái)不及做了…… 今天來(lái)復(fù)盤(pán)一下這次周賽“坐牢”的原因，希望以后注意改正。

1 背景

上上周的第 304 場(chǎng)周賽在比賽的時(shí)候 AK 了，但是賽后補(bǔ)的測(cè)試用例最后一題沒(méi)過(guò)，所以成績(jī)不是很好（2056 / 7372），競(jìng)賽分?jǐn)?shù)掉了 7 分。

所以上周末就想著要上分補(bǔ)回來(lái)。周六白天加班，晚上是第 84 場(chǎng)雙周賽，但狀態(tài)還算正常，四道題全過(guò)，排名 573 / 4574（就是提交錯(cuò)了 4 次多加了 20 min 有點(diǎn)懊惱）。然后就有點(diǎn)飄了，打完雙周賽就去玩《艾爾登法環(huán)》去了，熬夜到挺晚。

結(jié)果周日一覺(jué)睡到十點(diǎn)多，起床后趕緊把 IDE 開(kāi)好，洗漱完直接開(kāi)始周賽。感覺(jué)自己的比賽狀態(tài)受這一點(diǎn)影響還是挺大的，這樣昏昏沉沉狀態(tài)對(duì)于力扣周賽這種拼速度的競(jìng)賽（相較于自己日常刷題可以懶懶散散慢慢想）來(lái)說(shuō)就是大忌，這是日后必須要注意的一點(diǎn)——腦力勞動(dòng)之前千萬(wàn)不要熬夜……

2 過(guò)程

2.1 第一題

開(kāi)始比賽后，第一題就給自己埋下了坑。這里先復(fù)盤(pán)一下題目：

2367. 算術(shù)三元組的數(shù)目 難度：簡(jiǎn)單

給你一個(gè)下標(biāo)從 0 開(kāi)始、嚴(yán)格遞增 的整數(shù)數(shù)組 nums 和一個(gè)正整數(shù) diff 。如果滿(mǎn)足下述全部條件，則三元組 (i, j, k) 就是一個(gè) 算術(shù)三元組 ：

• i < j < k ，

• nums[j] - nums[i] == diff 且

• nums[k] - nums[j] == diff

返回不同 算術(shù)三元組 的數(shù)目。

示例 1：

輸入：nums?=?[0,1,4,6,7,10],?diff?=?3
輸出：2
解釋?zhuān)?br>(1,?2,?4)?是算術(shù)三元組：7?-?4?==?3?且?4?-?1?==?3?。
(2,?4,?5)?是算術(shù)三元組：10?-?7?==?3?且?7?-?4?==?3?。


示例 2：

輸入：nums?=?[4,5,6,7,8,9],?diff?=?2
輸出：2
解釋?zhuān)?br>(0,?2,?4)?是算術(shù)三元組：8?-?6?==?2?且?6?-?4?==?2?。
(1,?3,?5)?是算術(shù)三元組：9?-?7?==?2?且?7?-?5?==?2?。


提示：

• 3 <= nums.length <= 200

• 0 <= nums[i] <= 200

• 1 <= diff <= 50

• nums 嚴(yán)格 遞增

來(lái)源：力扣（LeetCode） 鏈接：https://leetcode.cn/problems/number-of-arithmetic-triplets 著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

怎么樣？你看了是否有思路呢？畢竟是簡(jiǎn)單題，而且有 nums 不超過(guò) 200 個(gè)元素的限制，所以直接

復(fù)雜度的三重 for 循環(huán)，或者 scala 里面的 combinations 方法（表示所有 C(3, n) 的組合，返回是一個(gè)迭代器）都可以通過(guò)。我最終通過(guò)的代碼如下（三重循環(huán)可以參考競(jìng)賽前幾名的代碼，大部分都是直接三重循環(huán)）：

看題解可以知道，更加好的選擇是使用哈希表一次遍歷：對(duì)于每一個(gè) nums 的元素都先驗(yàn)證元素減 diff 和減 2 * diff 是不是都在哈希表里，再無(wú)論如何把元素加到哈希表中。這樣算法的時(shí)間復(fù)雜度就只有

了。這個(gè)思路很好理解，這里我就不貼代碼了。

類(lèi)似的，同等時(shí)間復(fù)雜度還有雙指針一次遍歷的方法：把哈希表?yè)Q成兩個(gè)指示減 diff 和減 2 * diff 所在位置的指針即可。

然而我在比賽時(shí)，首先想到的就是三重循環(huán)的這種方法，但感覺(jué)時(shí)間復(fù)雜度太拉胯了，一時(shí)間又沒(méi)有更好的思路，就先跳過(guò)了第一題，直接做第二題去了。這就為后來(lái)最終成績(jī)很差埋下隱患：我們知道，力扣的單場(chǎng)比賽排名首先是按通過(guò)題目的總分來(lái)排，相等分?jǐn)?shù)再按最后通過(guò)時(shí)間來(lái)排（當(dāng)然還有錯(cuò)誤提交罰 5 min）。等我第三題坐牢回來(lái)做第一題時(shí)，已經(jīng)是一個(gè)小時(shí)后了，等于說(shuō)排名是按一個(gè)小時(shí)去和只通過(guò)前兩題的人排的……

所以，很重要的一點(diǎn)，能通過(guò)的題目一定要率先趕緊解決。不然遇上極端情況，回過(guò)頭來(lái)補(bǔ)前面的題目的通過(guò)時(shí)間成為了最后通過(guò)耗時(shí)的話(huà)，那還是很吃虧的。

其次就是注意觀(guān)察題目數(shù)據(jù)范圍，有時(shí)不必過(guò)于糾結(jié)時(shí)間復(fù)雜度。有時(shí)候數(shù)據(jù)量小的話(huà)，暴力也是可以通過(guò)的。但是看著我第一題 7888 ms 的通過(guò)時(shí)間，感覺(jué)也是挺玄幻的。（不知道會(huì)不會(huì)也補(bǔ)案例變成不通過(guò)……）

2.2 第二題

第二題通過(guò)還是很順利的，十三分鐘的時(shí)候就已經(jīng)提交通過(guò)了：

2368. 受限條件下可到達(dá)節(jié)點(diǎn)的數(shù)目 難度：中等

現(xiàn)有一棵由 n 個(gè)節(jié)點(diǎn)組成的無(wú)向樹(shù)，節(jié)點(diǎn)編號(hào)從 0 到 n - 1 ，共有 n - 1 條邊。

給你一個(gè)二維整數(shù)數(shù)組 edges ，長(zhǎng)度為 n - 1 ，其中 edges[i] = [ai, bi] 表示樹(shù)中節(jié)點(diǎn) ai 和 bi 之間存在一條邊。另給你一個(gè)整數(shù)數(shù)組 restricted 表示 受限 節(jié)點(diǎn)。

在不訪(fǎng)問(wèn)受限節(jié)點(diǎn)的前提下，返回你可以從節(jié)點(diǎn) 0 到達(dá)的 最多 節(jié)點(diǎn)數(shù)目。

注意，節(jié)點(diǎn) 0 不 會(huì)標(biāo)記為受限節(jié)點(diǎn)。

示例 1：

輸入：n?=?7,?edges?=?[[0,1],[1,2],[3,1],[4,0],[0,5],[5,6]],?restricted?=?[4,5]
輸出：4
解釋?zhuān)涸诓辉L(fǎng)問(wèn)受限節(jié)點(diǎn)的前提下，只有節(jié)點(diǎn)?[0,1,2,3]?可以從節(jié)點(diǎn)?0?到達(dá)。


示例 2：

輸入：n?=?7,?edges?=?[[0,1],[0,2],[0,5],[0,4],[3,2],[6,5]],?restricted?=?[4,2,1]
輸出：3
解釋?zhuān)涸诓辉L(fǎng)問(wèn)受限節(jié)點(diǎn)的前提下，只有節(jié)點(diǎn)?[0,5,6]?可以從節(jié)點(diǎn)?0?到達(dá)。


提示：

• 2 <= n <= 10^5

• edges.length == n - 1

• edges[i].length == 2

• 0 <= ai, bi < n

• ai != bi

• edges 表示一棵有效的樹(shù)

• 1 <= restricted.length < n

• 1 <= restricted[i] < n

• restricted 中的所有值 互不相同

來(lái)源：力扣（LeetCode） 鏈接：https://leetcode.cn/problems/reachable-nodes-with-restrictions 著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

思路很簡(jiǎn)單，DFS + visit 數(shù)組作為已訪(fǎng)問(wèn)和受限的元素的哈希表，直接計(jì)數(shù)即可。代碼如下（這里 DFS 的邏輯是使用隊(duì)列迭代實(shí)現(xiàn)的，沒(méi)有用遞歸）：

2.3 第三題

這下到了我“坐牢”的第三題了。說(shuō)實(shí)話(huà)事后看別人題解發(fā)現(xiàn)確實(shí)不難，但自己就是硬生生在這道題坐了一小時(shí)十五分鐘的牢。

2369. 檢查數(shù)組是否存在有效劃分 難度：中等

給你一個(gè)下標(biāo)從 0 開(kāi)始的整數(shù)數(shù)組 nums ，你必須將數(shù)組劃分為一個(gè)或多個(gè) 連續(xù) 子數(shù)組。

如果獲得的這些子數(shù)組中每個(gè)都能滿(mǎn)足下述條件 之一 ，則可以稱(chēng)其為數(shù)組的一種 有效 劃分：

1. 子數(shù)組 恰 由 2 個(gè)相等元素組成，例如，子數(shù)組 [2,2] 。

2. 子數(shù)組 恰 由 3 個(gè)相等元素組成，例如，子數(shù)組 [4,4,4] 。

3. 子數(shù)組 恰 由 3 個(gè)連續(xù)遞增元素組成，并且相鄰元素之間的差值為 1 。例如，子數(shù)組 [3,4,5] ，但是子數(shù)組 [1,3,5] 不符合要求。

如果數(shù)組 至少 存在一種有效劃分，返回 true ，否則，返回 false 。

示例 1：

輸入：nums?=?[4,4,4,5,6]
輸出：true
解釋?zhuān)簲?shù)組可以劃分成子數(shù)組?[4,4]?和?[4,5,6]?。
這是一種有效劃分，所以返回?true?。


示例 2：

輸入：nums?=?[1,1,1,2]
輸出：false
解釋?zhuān)涸摂?shù)組不存在有效劃分。


提示：

• 2 <= nums.length <= 10^5

• 1 <= nums[i] <= 10^6

來(lái)源：力扣（LeetCode） 鏈接：https://leetcode.cn/problems/check-if-there-is-a-valid-partition-for-the-array 著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

讓自己坐牢的思路是這樣的：三種有效劃分中顯然最特別的是第三種——連續(xù)遞增 1 的三個(gè)元素。中間的那個(gè)元素一定是單個(gè)的。那么我們可以把那些單個(gè)元素找出來(lái)，判斷它們是否滿(mǎn)足第三種情況。然后對(duì)于剩下的元素，我們看它們相同的元素是不是連續(xù)的即可（連續(xù)意味著 2 個(gè)以上，都可以拆分成任意個(gè) 2 或 3 的和）。

但是事實(shí)上，這樣做就要面對(duì)很多邊界情況：?jiǎn)蝹€(gè)元素是可以和單個(gè)元素組成連續(xù)遞增 1 的三個(gè)元素，也可以抽一個(gè)連續(xù)的元素來(lái)組成連續(xù)遞增 1 的三個(gè)元素，然后被抽取過(guò)的連續(xù)元素，就需要判斷是不是只剩下一個(gè)（這樣就又不可以了）。在不斷的提交和被邊界條件判不通過(guò)的反復(fù)中，時(shí)間最終被耗盡了。

實(shí)際上看題解就知道，動(dòng)態(tài)規(guī)劃其實(shí)很快就可以解決：

看狀態(tài)轉(zhuǎn)移能不能把 true 按照三種方式傳遞到最后即可。代碼很簡(jiǎn)單，思路很清晰。但自己比賽的時(shí)候就是掉入了無(wú)窮無(wú)盡的細(xì)節(jié)里面爬不出來(lái)了，也一直沒(méi)有重新跳出錯(cuò)誤的思路，導(dǎo)致本次周賽坐牢，體驗(yàn)賊差。

所以，比賽過(guò)程中，如果發(fā)現(xiàn)自己的思路導(dǎo)致邊界條件判斷繁瑣，無(wú)法有效解決題目時(shí)，就要及時(shí)重新審視自己的思路本身是否有問(wèn)題。方向比努力更重要啊……

2.4 第四題

第四題在比賽時(shí)沒(méi)來(lái)得及做，但是最后讓我看到了只是中等難度（心臟驟停）。知道不難卻沒(méi)有時(shí)間做，難受啊……

2370. 最長(zhǎng)理想子序列 難度：中等

給你一個(gè)由小寫(xiě)字母組成的字符串 s ，和一個(gè)整數(shù) k 。如果滿(mǎn)足下述條件，則可以將字符串 t 視作是 理想字符串 ：

• t 是字符串 s 的一個(gè)子序列。

• t 中每?jī)蓚€(gè) 相鄰 字母在字母表中位次的絕對(duì)差值小于或等于 k 。

返回 最長(zhǎng) 理想字符串的長(zhǎng)度。

字符串的子序列同樣是一個(gè)字符串，并且子序列還滿(mǎn)足：可以經(jīng)由其他字符串刪除某些字符（也可以不刪除）但不改變剩余字符的順序得到。

注意：字母表順序不會(huì)循環(huán)。例如，'a' 和 'z' 在字母表中位次的絕對(duì)差值是 25 ，而不是 1 。

示例 1：

輸入：s?=?"acfgbd",?k?=?2
輸出：4
解釋?zhuān)鹤铋L(zhǎng)理想字符串是?"acbd"?。該字符串長(zhǎng)度為?4?，所以返回?4?。
注意?"acfgbd"?不是理想字符串，因?yàn)?'c'?和?'f'?的字母表位次差值為?3?。


示例 2：

輸入：s?=?"abcd",?k?=?3
輸出：4
解釋?zhuān)鹤铋L(zhǎng)理想字符串是?"abcd"?，該字符串長(zhǎng)度為?4?，所以返回?4?。


提示：

• 1 <= s.length <= 10^5

• 0 <= k <= 25

• s 由小寫(xiě)英文字母組成

來(lái)源：力扣（LeetCode） 鏈接：https://leetcode.cn/problems/longest-ideal-subsequence 著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

因?yàn)榭紙?chǎng)上沒(méi)做，這里就直接附比賽之后自己寫(xiě)的通過(guò)代碼了：

重點(diǎn)要想到把時(shí)間復(fù)雜度轉(zhuǎn)嫁到固定的較小的數(shù)值上（本體是 26，即小寫(xiě)字符數(shù)量）—— 枚舉字符，然后動(dòng)態(tài)規(guī)劃，其實(shí)還是有點(diǎn)難想的。這里就不細(xì)說(shuō)了，主要還是總結(jié)周賽的失誤。

最后一點(diǎn)，那就是前面的問(wèn)題解決不了的時(shí)候，可以簡(jiǎn)單看看后面的題目。不過(guò)這一點(diǎn)就和第一題的行為起了沖突，當(dāng)時(shí)就是解決不了第一題，就跳到后面看第二題了。所以我們需要加個(gè)限定：在后面題目有頭緒時(shí)就做后面的試試看，不然就優(yōu)先把難度低的題目解決完。

3 總結(jié)

總之，這次周賽怕是要掉很多分，以后要好好吸取這次的經(jīng)驗(yàn)。最近也看了前幾名的大佬們的代碼，發(fā)現(xiàn)基本都是 C++ 居多。一方面當(dāng)然有算法競(jìng)賽訓(xùn)練一般都是使用 C++ 的原因；另一方面我感覺(jué)是因?yàn)閷?duì)于算法題來(lái)說(shuō)，語(yǔ)言其實(shí)不重要，最重要的還是在于思路清晰。語(yǔ)法糖帶來(lái)的幫助也許只是蠅頭小利，前提還是自己想明白了怎么做。自己還是要多思考，多總結(jié)，多復(fù)盤(pán)，這樣才有提高。

題外話(huà)：周賽“坐牢”讓自己周日心情很差，本來(lái)打算寫(xiě)點(diǎn)代碼或者文章的，結(jié)果下午和晚上基本都去打《艾爾登法環(huán)》了（捂臉）……