【Leetcode】279. Perfect Squares

1 BFS for the shortest path

2 先找到小于n的所有perfect squares

3 为什么这叫BFS呢?因为把所有情况都穷举完了

4 需要一个变量来记录path的深度,也就是返回值

5  BFS一般需要一个数组来存储这一行的中间结果

6 每次都用剩下的值去减list中的perfect square number,得到新一个level的值,当level中的值和list中的perfect square相等时,说这个path结束了,可以返回cnt了。

7 由于list中是ascending的,所以当list中的值大于当前余数时,可以直接跳出循环了;小于余数的话,就继续往下走

8 设置一个set,遇到重复的余数,直接只算一遍就行了


最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容