LeetCode Weekly Contest #87

比賽紀錄 1 分

Q1. Backspace String Compare

給定兩個打字字串 S, T
所謂打字字串表示一種只包含小寫字母和 ‘#’ 的字串，其中 # 代表 backspace 字元
問若將兩個打字字串輸入文字編輯器後顯示的結果是否相等？
例如，打字字串 “ab#c" 輸入文字編輯器的結果是 “ac"

兩邊分別去計算輸入文字編輯器的結果，
實作一個支援 push_back 跟 pop_back 的資料結構。

Q2. Longest Mountain in Array

若一個A 的 subarray B 滿足以下條件，則我們稱它是一座山：

  1. length 至少為 3 。
  2. 存在一個山頂 i 滿足 B[0], B[1], …, B[i] 嚴格遞增、B[i], B[i+1], …, B[length-1] 嚴格遞減、且 i 不為左右端點。

給定一個陣列 A ，找出最長的山。

若我們從山頂 i 的位置來找山顯然會比較方便，即固定 i 後分別找出左邊的遞增段跟右邊的遞減段長度。由於此兩段作法相似，以下只考慮找左邊遞增段部分。

若以 (i-1) 為山頂的遞增段長度為 k ，考慮 A[i-1] 跟 A[i] 的大小關係：

  1. A[i-1] < A[i] 那麼以 i 為山頂顯然可以接續這個山坡，故以 i 為山頂的遞增段長度為 k+1
  2. A[i-1] \geq A[i] 那麼以 i 為山頂不會有任何遞增段。

由此，我們可以從左到右透過 DP 計算出每個山頂的遞增段長度。
同理，從右到左 DP 可以計算出每個山頂的遞減段長度，依照這兩個數值算出以該位置為山頂的山有多長。

Q3. Hand of Straights

給一副至多 10000 張牌的手牌，每張牌都有一個 \left[ 0,10^9 \right] 範圍內的數值
希望將這副牌分成許多組，每組恰好包含 W 張牌且是一個順子，問是否能做到？

  1. 每次取出最小的數字 k。
  2. 檢查以該數字起頭的順子 k, k+1, ..., k+W-1 是否都在剩餘手牌中。
  3. 將該順子從剩餘手牌移除。

然後就看怎麼實作了，我用 dict 維護手牌移除、每次暴力取 min ，
現在想想應該不會過但反正我是過了。

Q4. Shortest Path Visiting All Nodes

給定一張 12 個點的無向無權圖，
輸出每個點都經過至少一次的最短路徑長。

經典的狀態壓縮 DP。

\text{DP}[i][\text{stat}] ：

  1.  i 表示當前路徑停在哪個點。
  2. stat 用 one-hot 紀錄哪些點已經走過 (1) 哪些點還沒走過 (0)。
  3. \text{DP}[i][\text{stat}] ：表示已經走過 stat 這些點，且最後停在 i 的最短路徑長度。

轉移就是枚舉所有在 stat 內的點 j ：

\text{DP}[i][\text{stat}] = \text{min}( \text{DP}[j][\text{stat without node i}] + \text{dist}(i, j) )

其中 dist 表示兩點間的最短路徑長，透過 floyd-warshall 演算法計算。

總複雜度 = 狀態 * 轉移 = O(N\times 2^N) \times O(N) = O(N^2 \times 2^N)

比賽紀錄

時間 錯誤 題號 其他
+5min Q1
+8min +4bug Q2 看錯題目
+16min +2bug Q3 python 的字典用不太熟
+21min Q4

發表者：poao899

已發表

發表留言