广度优先搜索之完全平方数广度优先搜索之完全平方数

完全平方数给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例 1:输入:n=12输出:3解释: 12 = 4 + 4 + 4.示例 2:输入:n=13输出:2解释: 13 = 4 + 9.

广度优先搜索的两个主要应用：遍历或找出最短路径。
12可以写成多个完全平方数相加的形式，比如12=4+4+4，12=4+4+1+1+1+1等等。可以看做从一个源点（12）出发，到达目标路径有多种选择，题目要求的是让组成和的完全平方数的个数最少，也就是让我们求最短路径。我们可以考虑把问题转换成图搜索的问题。
我们解决图的问题的第一步就是找出问题对应的图（Graph）。由于图是顶点和边的集合，因此找图的关键是找出图的顶点和边。对于这个问题，每一个平方数都是一个顶点（前提是它们相加等于输入的n）。每一个平方数相加等于输入的n，那么加号就相当于边。
解决图的问题的第二步是决定用什么顺序来遍历图。通常有两种不同方法遍历图，广度优先搜索和深度优先搜索。由于题目要求的是让组成和的完全平方数的个数最少，那么我们应该采用广度优先搜索算法。这是因为广度优先搜索是从源点开始首先达到所有距离源点为1的顶点，接着轮到达所有距离源点为2的所有顶点。根据广度优先搜索从源点到达某一顶点，那么一定是途径从源点到达该结点的最短路径。
下面是python代码：

from queue import Queueclass Solution(object): def numSquares(self, n): q = Queue() visited = [False for _ in range(n + 1)] #已经遍历过的节点存储在visited中Falese表示没有遍历过 steps = 0 #步数 q.put([n, steps]) #队列用来存储当前节点以及步数 I = 1 while not q.empty(): v, steps = q.get() #v是当前节点 nexts = self.getNexts(v, I) #nexts是一个列表，用来存储下一层节点 for next in nexts: if not visited[next]: visited[next] = True #添加尚未遍历的节点 q.put([next, steps+1]) #将下一次要遍历的节点都放入队列中 if next == 0: #当下一层节点的值为0时，也就是上一层的节点值为某个数的平方，返回步数，问题解决 return steps+1def getNexts(self, v, i): """ 获取下一层所有节点，并存储在列表nexts中，返回nexts """ nexts = list() next = v - i ** 2 while next >= 0: nexts.append(next) i += 1 next = v - i ** 2 return nexts

提交到LeetCode后结果如下：