营销网点号是什么意思/企业网站seo排名优化

题目：完全平方数
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
示例:
输入: n = 12，输出: 3 
解释: 12 = 4 + 4 + 4.
输入: n = 13，输出: 2
解释: 13 = 4 + 9.

-------------------------------------------------------------------------------

解法1#：神奇的 "四平方和定理"

四平方和定理说明每个正整数均可表示为4个整数的平方和。它是费马多边形数定理和华林问题的特例。

class Solution2(object):def numSquares(self, n):""":type n: int:rtype: int"""while n % 4 == 0:n /= 4if n % 8 == 7:return 4num = 0while num ** 2 <= n:num2 = int((n - num ** 2) ** 0.5)if num ** 2 + num2 ** 2 == n:return (not not num) + (not not num2)num += 1return 3

解法2#：利用广度优先遍历的逻辑

class Solution(object):def numSquares(self, n):""":type n: int:rtype: int"""q = []# 创建队列q.append([n, 0])  # [n,0] 代表当前节点的值和步数temp = [False for _ in range(n+1)]# 保存遍历过的结点temp[n] = True# 遍历队列里的节点while any(q):num, step = q.pop(0)i = 1left_num = num -i**2while left_num >= 0:# 最先达到0的一定是步数最少的if left_num == 0:return step+1# 只添加没有遍历过的节点if not temp[left_num]:q.append((left_num,step+1))temp[left_num] = Truei += 1left_num = num - i**2

参考：

https://baike.baidu.com/item/%E5%9B%9B%E5%B9%B3%E6%96%B9%E5%92%8C%E5%AE%9A%E7%90%86/4507832?fr=aladdin

https://blog.csdn.net/wangsiyu34567/article/details/82825475