LeetCode刷题笔记——BFS

279. Perfect Squares (bangbang)

这道题我看到之后的直观想法就是一个一维的动态规划问题，但是时间效率却是平方级别。这种结果在leetcode通常都是算慢的…但是也没考虑到更好的解法。看到BFS的标签才想到了一种宽度优先搜索解空间的方法。就是目标值一定可以拆出来一个平方数，然后我去看一个目标数怎么最快的拆出0。然后 discuss 区有一个思路是从 0 往上加，看怎么可以最快的通过完全平方数加到目标数，在这个方面上，这两种方法没有本质的区别。而重要的区别是我和黄同学讨论这道题的时候所发现的，我的思路是为了避免重现重复的计算，比如1+4=5,同样的，4+1=5。为了避免这种交换律导致的重复，我在搜索时通过人为规则保证路径上的数字递增或者递减。而 discuss 中的方法（其实也是BFS的正确思路），是通过visited避免重复路径。

542. 01 Matrix

这道题一开始黄同学问我从每个点都开始bfs会不会时间效率很低……然后我也没答上来，然后看了我自己的解法发现自己还挺厉害！诀窍在于一开始就把所有的 0 放进队列。