Leetcode 第 169 場比賽回顧

語言: CN / TW / HK

零、背景

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

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

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

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

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

一、不同數字之和為零

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

思路:前 n-1 個數字隨便給一個正數(比如遞增),最後一個數字補負數即可。

二、二叉樹所有元素

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

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

三、跳一跳遊戲

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

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

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

思路:搜尋即可, DFSBFS 都可以。

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

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

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

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

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

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

思路:典型的 DFS 題。

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

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

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

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

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

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

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

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

可惜樣例還是超時。

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

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

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

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

然後我就做完題了。

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

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

五、最後

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

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

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

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

-EOF-

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

個人微訊號:tiankonguse

QQ演算法群:165531769(不止演算法)

知識星球:不止演算法