算法

算法練習 Leetcode 力扣 1293 Shortest Path in a Grid with Obstacles Elimination 解法

問題 題目在這。 解題思路 格子題,從左上到右下需要的最小步數。難點在給了個預算k,最多可以穿牆k次。找距離需要用BFS,不走回頭路就可以,比較簡單。但是這題在空間上是有可能走回頭路的,因為除了空間以外,還多了個狀態是已經穿牆幾次。放到queue裏面的應該是(坐標,穿牆次數)的tuple。所以關鍵在於不要把相同(坐標,穿牆次數)放queue里,不然會無法停止。 Python解法

算法練習 力扣 150. Evaluate Reverse Polish Notation

問題總結 這題比較簡單,如果學過computer architecture,這個Reverse Polish Notation (RPN)基本就是個stack machine。很像彙編語言。用stack就可以解決。 坑 除法要求 that division between two integers should truncate toward zero. 測試數據裏面有負數, python裏面整數除法結果如果是小數,約成整數後是往小的方向約的。比如-0.4會變成-1,題目要求往0約,也就是-0.4變成0。用int(a/b)可解決。一個冷門知識。 Python解法

算法練習 Leetcode 力扣 322. Coin Change 解法

leetcode 322 coin change

題目在這裡。 自己想的答案,bottom up dp不太好想,從top down + cache開始,寫了幾次,每次簡化一點,最終寫成這樣通過OJ。 Python 版本。 為了更好理解算法,加了些log,記錄dfs被call了幾次和cache hit,和每個cache key被寫入次數(使用cache和不用cache的情況。 用coins = [1, 2, 5]和amount = 11為例子 用了cache 不用cache 運行完後cache的內容如下 正是從0到11每個amount的最少硬幣數。從此出發,想到bottom up dp正是需要構建如上cache的內容。dp[0] = 0,amount是0,當然一個硬幣不用。dp[amount]就看amount – coin值是不是正,而且之前是否有非-1的值。當算到amount的時候,前面dp[0]到d][amount-coin]都算過了。對所有的coin值都算一遍,把所有dp[amount – coin]的非-1最小值找出來,加1,就是dp[amount]。時間複雜度為O(amount * len(coins))。空間為 O(amount)。 過了多日以後自己重新想的Python寫法, 看看是否已經內化並掌握. 對比上面, 做了一些改進, dp list…
Read more