Leetcode第134場比賽回顧
一、背景
上週末因為五一調休加班,我沒有參加比賽,現在來看一下這個比賽吧。
做完做了這四道題,順便使用了一下 LeetCode 互動專案。
操作之後,發現杜宇首次使用 github 來協同工作的人來說,還是蠻有難度的。
如果你想學習演算法的話,建議參考上一篇文章《 啟動Leetcode演算法互動程式設計專案 》來嘗試一下。
如果你參與這個專案了,並參與了幾輪互動程式設計。以後也可以說自己在 github 上參與過公開專案了,而且還多次進行 pull request 貢獻程式碼了。
二、移動石子直到連續
題號:5039
題意:數軸上有三個不重複的數字 x<y<z
,每一步可以選擇 x
或者 z
數字來移動,移動位置後的新位置是 k
,需要滿足 x<k<z && k!=y
,直到無法移動,結束移動。
要求輸出最大移動步數和最小移動步數。
思路:首先需要明白,無法移動的條件是三個數字連續,即 x+1 == y && y+1 == z
。
而對於最大步數和最小步數,方案有兩種。
第一種方案是DP或記憶化搜尋。
但是看到這道題難度是 easy,搜尋和DP的難度至少是 Medium 或者 hard 的。
所以這道題肯定可以更簡單的方法。
第二種方案就是貪心計算。
先開最大步數,每移動一下, x
和 z
的距離至少減一,這樣移動到距離是2的時候,就不能移動了。
所以最大步數是 z-x-2
。
對於最小步數,通常兩步即可完成。
起始是x, y,z
第一步之後是
x,x+1,y
第二步之後是 x,x+1,x+2
但是,有時候需要一步就可以達到三個數字連續。 大概分這樣幾種情況:
1. x,x+1,x+2+n
,此時最後一個數字移動到 x+2
即可。
2. x,x+2,x+2+n
,此時最後一個數字移動到 x+1
即可。
3.兩種對稱情況,即後兩個數字連續或者間隔為1。
只有一種情況需要0步,即三個數字本身就是連續數字。
小技巧:對於只有一步的情況較多,可以使用排除法,兩步和零步的都計算了,其他的就是一步的。
三、邊框著色
題號:5040
題意:給一個矩陣和一個座標,求將座標值相等的聯通區域染色,這裡只需要染色邊界。
思路:如果是純粹的染色,大家應該都會做,一個 DFS 或者 BFS 即可。
那隻染色邊界怎麼辦呢?
染色前判斷一下是不是邊界即可。
小技巧:新染色的值可能在矩陣上是存在的,有些人不知道怎麼區分。
我經常使用的方法時先染色為矩陣上不存在的特殊值,最後再全部替換為目標值。
四、不相交的線
題號:5041
題意:給兩個陣列,兩個陣列之間相等的值可以相連。問不相交的線可以畫幾條。
思路:這道題就是一個赤裸裸的最長公共子序列題。
直接兩層迴圈 DP 即可。
五、逃離大迷宮
題號:5042
題意:告訴你一個 10^6 x 10^6
大小的網格,以及一些座標代表障礙物,問是否可以從一個起點到達一個終點。
思路:以前做過類似的題,不過矩陣較小,直接暴力搜尋即可。
這裡矩陣很大,沒辦法暴力搜尋了。
那怎麼判斷兩個點是否可到達呢?這個不好判斷。
但是反過來,我們可以判斷這個點是否不可達。
當障礙物將其中一個點圍起來的時候,這個點就會變成不可達。
看看障礙物的個數,最多兩百個。
不考慮邊界,那這些障礙物最大可以圍城一個 50*50
的閉環空間。
結合上邊界,這些障礙物最大可以圍城 200*100
的閉環空間。
看到這裡,這道題的解決方案也就出來了。
我們分別查詢兩個點,如果在 200*100
步內依舊還有搜尋空間,則認為這個點是開放的。
如果兩個點都是開放的,則認為兩個點是可以互相到達的。
六、最後
這次四道題還算簡單,尤其是介紹思路後,大家都可以實現一下。
和幾個人簡單的互動後,發現 github 上的 network 圖很好看,可以清晰的記錄大家的互動情況。
你可以來嘗試一下。
-EOF-