Monthly Archive: June 2020

這題還是挺難寫對的。經過幾番嘗試以後，發現最好理解的演算法就是先對group做一次拓撲排序。然後按group的順序，對每個group里的items的做拓撲排序。這題增加另一難點在於gorup是-1的情況。其實相當於每個-1都是自己的新group。於是大量的工作其實在建立group的dependency graph上。拓撲排序的函數可以寫一次反覆重用。Python解法如下： 本題是複合題，三個點：1. 拓撲排序本身，然後分別用在group level和每個group的item level2. 建立group dependency3. handle group == -1的情況，就是給每個這種item assign新group

這題不知道為什麼被標記為topological sort，但其實和topological sort沒什麼關係，只是DFS。Implementation確實和DFS的topological sort有點像，但是因為沒有graph的dependency關係，其實還是不一樣的。不過cache的使用上確實有相似性。以下是我寫得比較滿意的python解法 要點總結： 用這種方式初始化cache比較簡潔 ，新學到的 cache = [[0] * len(line) for line in matrix] 用nested function大大減少需要傳遞狀態的參數 nonlocal max_l可以讓nested function直接改變外面的參數很方便，所以在外面call dfs的時候連return都不用處理 dirs = [(1,0), (-1,0), (0,1), (0,-1)]，i2 = i + d[0]，j2 = j + d[1]處理方向。以前都是手寫上下左右，太啰嗦而且容易出錯。這種方法對2維DFS很適用。

這題基本和269 alien dictionary一樣，難度為medium。其實269 alien dictionary比這題多了就是建graph的過程而這題的graph基本是已經給定的。重點還是topological sort部分。比207. Course Schedule多了兩行handle sort部分。以下為同樣思路的python解法，比較簡短，容易寫對。

這題以前覺得特別難，其實是簡化版的topological sort，也就是只需要判斷有沒有環(circular dependency)和省掉了sort部分。可以用269 alien dictionary同樣的DFS思路加以簡化而成。 這是最近寫得比較滿意的python解法。 對比一下大概半年前寫得當時比較滿意版本，其實演算法差不多。有如下小改進讓code更短了：1. seen用了Tree和False表示走通了的和當前正在走的路徑，比原來的更省事。看來2種狀態是判斷環和避免重新走原來走過的路所必要的。2. 節點全部寫進edges裡面，edges = {c: set() for c in range(numCourses)} ，不管有沒有dependency，省了 if i not in deps: 判斷3. 需要order的話，dfs參數start, edges, seen order。不需要的話order的話就省掉order，只要start, edges, seen。用函數內定義函數可以少寫很多用來傳遞狀態的參數。

這題本質上是一個拓撲排序topological sort，需要判斷有沒有環來處理無效input，難度主要來自這部分。Topological sort可以用dfs解決，但是沒練習過還不不容易寫對的。先上一個我比較滿意的python解法。 總結一下要點。1. edges = {c: [] for word in words for c in word} 這種一行兩個循環建map的方式我也是新學的，很方便。這個map key是排前面的字母，value是排後面的字母。而且不管有沒有後面的，key都加上了，這樣省了另一個變數存字母表，可以對比我之前一個寫對不那麼好的解法。2. 用zip遍歷pair很好用，減少了出index bug的可能3. len(word1) > len(word2) and word1.startswith(word2)，這是一個特殊的case。比如abc排在ab前面，不管什麼字母表順序，就是c排在空前面，那是無效的。4. seen的利用，這是最巧妙的地方。寫了幾種嘗試，發現環不太容易。如果只用一個set記錄visited，就無法區分是一條已經走通的路還是當前這條路又回到某個之前經過的一點。解法方法可以用一個set記錄visited，只加不減，另一個set記錄當前這條路的路徑，回溯時要更新，比較麻煩。這種解法利用了False和True兩種states，False代表正在走的路，True代表以前已經走到底能走通的路。非常深刻，我想了很久才算大概理解。5. if not all(dfs(start) for start in edges)，all是個我新學的function，input是collection或者更準確說是可以iterable的東西，就是要每個元素都是true就是true。換句話說就像開關串聯。本來我寫得是all([dfs(start) for start in edges])，後來發現代表list的方括弧可以省略，估計是些語法糖。Python裡面確實有很多我不知道的語法糖。6. dfs是函數內定義的函數，可以省了self和用內函數外的變數保存狀態，不用每個recursion call都pass一次。 做完這題後，重新做course…
Read more

到python官方網站，下載macOS 64-bit installer 。 下載完成後雙擊.pkg文件安裝既可 我這原來的/usr/bin/python3 還是3.7 怎樣在pycharm里使用？ Setting裡面（cmd + ,) search interpreter，選project interpreter 添加成功後 怎樣創建virtual environment? python 3.8.3有什麼新特性？ 新添了類型提示。

和add binary基本一樣。 關鍵點：從右邊開始加把長的input作為第一個，給最左邊加0用來進位（如果需要的話），最後看要不要去掉python裡面要用ord，chr 來做char/ascii轉換 python解法

和add strings基本一樣。 關鍵點：從右邊開始加把長的input作為第一個，給最左邊加0用來進位（如果需要的話），最後看要不要去掉python裡面要用ord，chr 來做char/ascii轉換 python解法

會把這個key加入到unordered_map裡面，value是數據類型的default值。比如int就是0，string就是””。