LeetCode0279.完全平方数[Medium][Python][BFS]ProblemLeetCode给定一个正整数n，找出最少的完全平方数（例如1,4,9,16,...)总和为n。例1：输入：n=12输出：3解释：12=4+4+4。例2：输入：n=13输出：2解释：13=4+9。题目给定一个正整数n，求几个完全平方数字（例如1、4、9、16，...），以便它们的总和等于n。您需要尽量减少构成总和的完全正方形的数量。示例1：输入：n=12输出：3解释：12=4+4+4。示例2：输入：n=13输出：2解释：13=4+9。想法解决方案-BFS将每个整数视为图中的节点，如果两个整数之间的差是一个平方数，则说明两点之间存在边连接。求最小二乘数就是求n到0的最短路径，所以可以用BFS。时间复杂度：O(n^2)空间复杂度：O(n^2)Python3codeclass解决方案：defnumSquares(self,n:int)->int:#解决方案一：BFSq=[(n,0)]visited=[Falseforiinrange(n+1)]#初始化所有Falsevisited[n]=Truewhileany(q):#any：如果所有元素都为False，则返回False，否则返回Truenum,step=q.pop(0)i=1Num=num-i**2whileNum>=0:ifNum==0:returnstep+1ifnotvisited[Num]:#notvisitedq.append((Num,step+1))visited[Num]=Truei+=1Num=num-i**2解二四平方和定理拉格朗日四平方定理：任何正整数都可以表示为不超过四个整数的平方和。所以答案只能是：1,2,3,4。还有一个定理：满足四数平方和定理的数n（这里必须由四个数组成，小于四的一定不能）,必须满足n=(8b+7)*4^a。所以先缩n。然后判断减少后的数是否可以由两个平方数之和或一个平方数组成。如果不能，我们返回3，如果可以，我们返回平方数的个数。Python3代码类解决方案：defnumSquares(self,n:int)->int:#解决方案二：拉格朗日四平方定理whilen%4==0:#reducenn/=4ifn%8==7:return4a=0whilea**2<=n:b=int((n-a**2)**0.5)ifa**2+b**2==n:return(notnota)+(notnotb)#a和b是否为正整数a+=1return3代码地址GitHub链接
