Leetcode 第 169 場比賽回顧

零、背景

這次比賽都是大水題，不過最後一題是搜尋題，卡的是剪枝演算法。

很多人找不到有效的剪枝策略，導致過不了了吧。

其實剪枝策略就兩個，我選擇了第一個超時，換成第二個就過了。

因此有幸進入全球前 100 名了。

下面來看看這四道大水題吧。

一、不同數字之和為零

題意：給一個數字 n ，求構造 n 個不同的數字，使得這些數字之和為 0 。

思路：前 n-1 個數字隨便給一個正數（比如遞增），最後一個數字補負數即可。

二、二叉樹所有元素

題意：給兩個二叉樹，求所有元素組成的即可，按升序輸出。

思路：先分別遞迴獲取兩個二叉樹的值，排序即可。

三、跳一跳遊戲

題意：給一個數組 arr 和起始位置 i 。

我們可以從起始位置跳到 i + arr[i] 和 i - arr[i] 。

問這樣不斷的跳下去，是否可以遇到值為 0 的位置。

思路：搜尋即可， DFS 和 BFS 都可以。

四、字母與數字之間的難題

題意：給一個字串陣列以及一個目標字串。

當每個字元 A-Z 對映到互不相同的數字 0-9 後，字串就轉化為了數字。

問數組裡的數字之和能否等於目標數字。

樣例：給一個字串 ["AA", "BB"] ，目標數字 "CC" 。

則 A=>1 ， B=>2 ， C=>3 可以滿足 11+22=33 。

思路：典型的 DFS 題。

但是考慮到字串長度是 10 ，複雜度可能高達 10^10 。

這樣肯定會超時，所以需要剪枝。

考慮到不允許有字首零，我便想到從高位到低位列舉，然後檢查是否有字首零。

有了直接減掉，可惜最後一組樣例超時了。

已經從高位到低位列舉，順勢可以想到，預先判斷當前狀態是不是肯定不存在答案。

什麼時候不存在答案呢？ 就是目標字串以後不管怎麼取值，肯定小於前面的陣列的和。

具體來說，對於目標字串，沒有列舉的字元假設值是 9 ；對於列舉的字串，沒有列舉的字元假設值是 0 。

這樣目標字串的最大值如果還小於陣列的和，那就肯定沒答案了。

可惜樣例還是超時。

然後大部分人到這裡就沒辦法了。

我也是冥思苦想，然後想超時的原因可能是從高位剪枝，可能滿足的列舉量太多了。

如果從低位剪枝，必須嚴格相等，是不是滿足的列舉量就少多了呢？

於是我再次修改程式碼，沒想到測試樣例瞬間就出來了。

然後我就做完題了。

由於這個做了大量的預處理，程式碼量比較大，就不貼出來了。

想要程式碼的可以後臺回覆 weekly-contest-169 獲取這次比賽的原始碼。

五、最後

這次比賽前三題太水了，我這蝸牛般的敲程式碼速度，都可以在12分鐘做完，那你們應該都是10分鐘內吧。

最後一題雖然在剪枝上卡題了，對於我來說卻是一個機會。

以後應該再也沒有機會進去全球前百名了吧。

PS：後臺回覆 weekly-contest-169 獲取這次比賽四道題的原始碼。

-EOF-

本文公眾號：天空的程式碼世界

個人微訊號：tiankonguse

QQ演算法群：165531769（不止演算法）

知識星球：不止演算法