Leetcode 第 164 場比賽回顧

零、背景

大概從雙十一開始，leetcode 上的比賽題風突然全部變了，變得簡單了。

有人說這是因為美帝外企跳槽季來了，比賽的題難度與面試難度對齊了。

當然，這種小道訊息也沒人知道真假，我也不關心真假。

我們關心的是題的題自身的好與壞，以及涉及的演算法是否有意思。

下面來看看這幾道題吧，都是舊題，之前的比賽中都出現過類似的體型。

一、訪問所有點的最小時間

題意：座標軸上給 n 個點，問按順序遍歷這些點需要的最少時間。

規則：從一個點移動另一個點時，只能垂直上下左右，以及45度斜著走。

思路：如果只能垂直上下左右，那時間就是水平距離加上垂直距離。

由於可以斜著走，每斜著走一步，水平方向和垂直方向都減少一步。

所以我們需要儘可能斜著走。

那能斜著走多少步呢？

水平距離與垂直距離的最小值就是能夠斜著走的最大值。

不能斜著走了，則只剩下垂直方向或者水平方向，直線走過去即可。

那最終需要多少步呢？

假設水平需要 a 步， 垂直需要 b 步， 且 a 小於 b。

那麼最有答案就是 斜著走 a 步， 垂直走 b-a 步， 合起來就是總共走 b 步。

由此就可以得出結論：最優解是垂直距離和水平距離的最大值。

二、統計可以通訊的伺服器

題意：給一個矩陣，1 代表座標有一個伺服器，0 點沒有， 求可以通訊的伺服器數量。

規則：伺服器可以和相同水平線或者垂直線的其他伺服器通訊。

思路：一個伺服器能不能通訊，只需要判斷水平方向和垂直方向有沒有其他伺服器。

方法一：最簡單的就是按照題意暴力列舉每個伺服器是否可以通訊。

複雜度分析：矩陣有 n^2 個節點，判斷需要 n 次 複雜度：n^3

方法二：進一步分析，可以發現，當一行至少有兩個伺服器時，這一行的伺服器都是可以通訊的。

所以可以預處理統計出每行和每列的伺服器數量，然後就可以快速知道每個座標是否可以通訊了。

複雜度：n^2

三、搜尋推薦系統

題意：給一個字串陣列以及一個待搜尋的字串。

需要設計一個推薦系統，在依次輸入待搜尋字串的字母后，從字串陣列中搜索出字首匹配的字典序最小前三個字串。

思路：這個類似於電子翻譯詞典，根據輸入的字母，下拉列表會實時動態的變化。

其實這個是典型的字典樹，之前我曾在三個比賽中介紹過了。

可是，在之前的比賽中我也介紹了，我不想裸寫字典樹，而這個還需要維護前驅和後繼，更麻煩。

之前我自創的使用陣列上二分查詢來代替字典樹，可以完美的和字典樹等價起來，但我也不想敲了。

畢竟程式碼量有點大，我敲程式碼速度慢，敲完比賽就結束了。

於是我先做最後一題去了。

最後一題敲完，再一看這道題，發現暴力就可以直接過這道題。

下面就來看看這些方法吧。

方法一：具有前驅和後繼的字典樹。

複雜度分析：n 個查詢，每個查詢是字首長度。 綜合複雜度：n^2

方法二：有記憶的字典樹

使用字典樹裸搜的話，由於每次查詢是獨立的，導致有很多冗餘查詢。

冗餘的地方在於，這次查詢時，字首實際上已經在上次查詢過了。

如果上次查詢的資訊儲存下來，這次就可以在上次的基礎上進行查詢，這樣複雜度就較低了。

綜合複雜度：n

方法三：陣列加二分查詢模擬字典樹。

這個方法我在《 Leetcode 第133場比賽回顧 》裡介紹過，這裡就不介紹了。

由於是模擬字典樹，那就可以和優化後的字典樹完全一樣。

複雜度： n log(m)

方法四：記憶化陣列

這道題的查詢很特殊，都是一個字元竄的字首。

如果帶查詢的集合排好序的話，字首長度每增加一，滿足條件的集合就縮小一點。

那維護一個滿足條件的有序集合的複雜度多高呢？

上一個方法是二分查詢，複雜度是 n log(m)

這裡沒有二分查找了，複雜度就是 n*m 了

但是由於集合大小是 m，累計縮小的個數也不超過 m。

均攤複雜度竟然神奇的轉化為了 n + m 。

方法五：暴力二分查詢

先對字串陣列排序，題意要求匹配的前三個，那就對整個陣列二分查詢找到滿足條件的第一個。

複雜度： n log(m)

四、停在原地的方案數

題意：給一個長度為 len 的水平線，起始位置在 0， 合法區間是 [0, len)。

每次操作可以左移、右移、原地不動。

經過 n 次操作後，就形成了一個操作路徑。

求最終位置在原點 0 的操作路徑數。

思路：典型的動態規劃題。

在《 Leetcode 第 158 場比賽回顧 》的第三題 有限制的擲骰子 有點類似。

可以遞迴實現，也可以遞推實現。

而且對於路徑相關的動態規劃題，遞推更容易些。

這次比賽我就是這樣實現的。

遞推複雜度：n*m

實際上，這類遞推的動態規劃題，可以使用矩陣冪優化。

在《 有限制的隨機數（矩陣狀態機） 》中詳細介紹了怎麼使用矩陣冪解決這類問題，大概感興趣的話可以看看。

當然，這道題不適合矩陣冪優化，因為狀態太多，移動次數太少。

五、最後

這次比賽的後兩題都很適合來當做面試題，大家可以好好研究一下。

PS1：這周比較忙，上一場比賽我遲遲沒擠出時間來寫文章。

相關題解我就發現免費的演算法星球裡面了，剛興趣的可以去看看。

PS2：上次樊登讀書抽獎後，中獎者好像沒有聯絡我，獎品三天後就到期了，到時候就作廢了。

-EOF-

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

個人微訊號：tiankonguse

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

知識星球：不止演算法