LeetCode Weekly Contest #86

比賽紀錄 1 分

睡過頭…

Q1. Magic Squares In Grid

給定一個 100 x 100 2d-array，
問有多少 3 x 3 sub-array 是魔方陣。
(即 行列對角線總和都相同 且數字 1~9 不重複。)

這種範圍超小的拼速度題目重點變成了怎麼寫比較快，
直覺的做法有兩種：

  1. 直接靠定義作，每個 sub-array 檢查八條跟數字範圍。
  2. 因為 3×3 魔方陣只有下面這種 (跟他的旋轉鏡射) ，直接做 pattern matching 。
    \left[ \begin{matrix} 8 & 1 & 6 \\ 3 & 5 & 7 \\ 4 & 9 & 2 \\ \end{matrix} \right]

由於 2. 還要做矩陣的八種旋轉鏡射，這題寫 1. 快很多。
只要對每個 3×3 sub-array 檢查行列對角線皆為 15 且數字符合範圍即可。

Edited: 簡單解釋一下 15 怎麼來的好了：
設總和為\text{val}，考慮一個合法魔方陣a：

\left[ \begin{matrix} a_{00} & a_{01} & a_{02} \\ a_{10} & a_{11} & a_{12} \\ a_{20} & a_{21} & a_{22} \\ \end{matrix} \right]

只看橫向我們有
\text{val} = a_{00} + a_{01} + a_{02}
\text{val} = a_{10} + a_{11} + a_{12}
\text{val} = a_{20} + a_{21} + a_{22}

將三條相加可以得到
3 \times \text{val} = \Sigma a = 1 + 2 + ... + 9 = 45
\text{val} = 15

Q2. Keys and Rooms

有許多房間，每個房間都有其他房間的鑰匙。
你一開始在房間 0 ，問你能不能進入所有房間。

非常明顯的純 BFS 題，事實上這根本是直接給你 adjacency matrix 的意思。

Q3. Split Array into Fibonacci Sequence

將一個 digit 串 拆成 >=  3塊，
滿足剛好由左而右形成類似費氏數列的關係。
例如 “110111122335588143″ 拆成 [11, 0, 11, 11, 22, 33, 55, 88, 143]

串長度至多 200 ，所以我們一樣方便實作為主。

因為要處理 leading zero 問題，
最簡單的想法當然是把整個數列以整數方式儲存後再轉為字串，作字串比對。
這樣單一次比對的複雜度是 O(length) ，顯然很充裕。

那麼就只要枚舉前兩項 F1, F2 即可。
如此總複雜度大概 O(length^3)

Q4. Guess the Word

給你一個 100 words 的字典，單字長度都是 6。
對方已經想了一個字典內的單字作為答案，你要在 10 次 guess 中猜到它。
你每次 guess 可以猜一個單字，他會告訴你你選的單字跟答案比對結果 (match)。
例如 答案為 “abcdef" 你 guess(“abccfe") 會得到 3

每次 guess 都是要從指定 wordlist 中選一個單字來，有什麼做法能比隨機選擇更好？
因為字典在我們這邊，可以每個單字都選來跟全部單字比對，看 match 的分布哪個最好。
判斷 match 的分布哪個最好 最單純的想法就是 minmax (minimize maximum value)。

拿到 match 結果後，把不符合的單字踢出 wordlist 然後反覆猜測。
如此即是一個乍聽之下還算優秀的策略，實際上也能順利通過測試。

簡單估一下時間複雜度：
每次 guess 需要枚舉選取的單字，每次單字需要跟全部其他單字比對，
總複雜度 O(10\times N^2\times 6)

(第一次寫的時候根本沒有minmax，固定 guess index 0 當然的錯了)

Edited: 這題 random sample 單字來 guess 就會通過測試了。

比賽紀錄

時間 錯誤 題號 其他
+26min              Q1 睡過頭
+11min               Q2 python 的 queue 怎麼用啊 … 臨時改用 c++ 寫
+15min               Q3 python 的字串用不太熟
+16min +1bug Q4 沒有 minmax 是因為 min 的初始值寫錯 …

發表者：poao899

已發表

發表留言