[LeetCode] 用 Spotify 舉例輕鬆理解 #3 Longest Substring Without Repeating Characters
其實解答的程式碼看了一下還滿好理解，但是如果對於剛學程式的我鐵定是看了很痛苦，一堆字串的位置處理，就算看到解答還是不會自己寫。
所以我今天來挑戰更難的: 如何讓其他人理解自己寫的 code，就像最近看的文章 Things You Should Never Do, Part I 裡面說的一樣:
It’s harder to read code than to write it.
但其實不只這樣，有的時候光看 code 也是看不懂，這時候我們想要去讀 spec 就會發現根本沒有 spec。就算當初寫程式的人還在，跑去問他他可能會說: "這段 code 是我剛進公司寫的耶，我早就忘記我當初怎麼寫這段 code 了"，所以我覺得可以把上面的話延伸一下:
It's harder to find specs than to read code.
對於這麼生硬的 LeetCode 題目，我們有辦法做出易懂的 spec 讓人超好理解嗎?
用 Spotify 播放清單理解 LeetCode #3
我在 Spotify 上面隨機聽歌，聽到好聽的歌我就想加到我自己的清單:
每首歌我都用第一個單字來當代號好了。隔了一個禮拜我又聽到 On The Ground 覺得超好聽的 (假設而已，實際上我覺得還好)，我想要加到我的清單，想要每次放就第一個聽到:
可是清單裡面已經有 On The Ground 了，每次聽到他我就知道下一首是 Peaches，再下一首我也知道是什麼歌，相信大家應該經常有這種經驗。所以我把有重複的後面的歌也一併刪除:
這樣至少我的清單裡面都是還算新的順序，怎麼聽都不會膩，也猜不到下一首歌是什麼。
OK，問題來了:
給你一堆好聽的歌要加，照上面這樣做的話，你能找出最長的清單多長嗎?
例如有人常常長途旅行在車上放歌，當然希望清單越長越好，又不想要聽到聽過的順序。這就是 LeetCode #3 在解的問題。
用 PowerPoint 做 Spec
我還記得學軟體工程的課的時候常常要練習寫 spec，就會像網路上隨便找 design spec template 就會找到像這種的:
(ref)
但這其實還是太抽象了，就算加了一堆 diagrams 也一樣還是很抽象。
我們有辦法做得更好嗎? 有辦法做出讓任何人來一看就懂的 design spec 嗎? 如果我用投影片這樣做呢?
我也不用特別寫很多文字，看圖就可以理解我只是想用一個 "start" 變數來去記清單的開始位置在哪，我沒有要去動 string 代表的清單。position list 也不用特別去把舊的東西刪除，只要和 "start" 比較大小就知道他是不是已經被刪除了。
其實公司有很多內部文件都是利用投影片來當 programmer 的 design spec，丟給同事一看人家就知道你想做什麼，任何人看了 design spec 都應該要寫得出來程式。
來實作 C++ 程式碼
以前最好玩的部分就是寫程式，但是當你把 design spec 都做得超好理解，寫程式就變得很無聊了。這步驟只不過是最後一步，把一些架構上或命名上的東西顧一顧，然後測測看有沒有問題。
class Solution {
public:
int lengthOfLongestSubstring(std::string songList) {
int maxPlaylistLength = 0;
int songPos[128];
for (int i = 0; i < 128; i++) {
songPos[i] = -1;
}
int start = 0;
for (int i = 0; i < (int)songList.length(); i++) {
const char song = songList[i];
if (songPos[song] < start) {
// Unique song, join our playlist!
} else {
// Sorry the song is already in the playlist
const int oldSongPos = songPos[song];
start = oldSongPos + 1;
}
// Update the position of the new song
songPos[song] = i;
// Check if the new playlist is longer
const int numSongsInPlaylist = i - start + 1;
if (numSongsInPlaylist > maxPlaylistLength) {
maxPlaylistLength = numSongsInPlaylist;
}
}
return maxPlaylistLength;
}
};
這其實就和 LeetCode 上面的解答差不多，只不過我帶入了 playlist 的概念進去，而且我完全沒用一些 STL containers。如果還是不好理解可以看 GitHub 上面我有做一份更多註解的程式碼。
結果其實也還不錯，又快又省記憶體，更棒的是我們拉高了可讀性:
結語
寫程式不難，但有時最難的就是要兼顧以下的東西:
- 可讀性 (maintainability)
- 程式的效率 (performance)
- 趕快寫出來 (deadline!)
我曾經寫過個小 function 用了各種恐怖的技巧去最大化效率，雖然我覺得我有顧到可讀性，但是最後 code review 還是被說太難懂。
不過好險我有做 design spec 投影片，所以同事看了看之後其實也知道我想做什麼，他建議一個雖然沒辦法最有效率的演算法，但可讀性可是大爆發，連我也驚訝了一下竟然沒想到有這麼簡單的做法，後來就改成他建議的方式。
不過其實最難的部分我一直沒說，就是如何想出用 playlist 來說明這個艱澀難懂的 LeetCode 題目。我想了老半天有什麼東西是一連串，但是重複又要把舊的東西刪除，啊! Playlist!
留言
發佈留言