算法

算法练习 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