Leetcode 第 164 場比賽回顧

語言: CN / TW / HK

零、背景

大概從雙十一開始,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(不止演算法)

知識星球:不止演算法