【Leetcode】 322. Coin Change

1 特别注意amount=0的时候,是返回0,不是返回-1


2 以上BFS方法总是超时

3 因为很容易出现之前操作过的再次操作,这样就很耗时,像下图中的9,在第二行访问过,再第三行又出现了,因为之后的操作会是一模一样的,所以用一个visited的数组来存储是否被访问过




1 要注意corner case:当amount==0的时候,返回0,表示有0种组合方式

2 还有就是如果amount在coins中,直接返回1

3 queue中压栈money和dist

4 重点在什么时候加到visited中去,只有没有在visited中,才加入到visited中和放入队列中去



1 当amount是0的时候,返回0,不是-1

2 初始化dp的时候,float("inf")要用中括号括起来

Time complexity:O(amount * n) + O(nlogn) n is the length of coins

Space complexity: O(amount)

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

友情链接更多精彩内容