【LeetCode 中等题】90-完全平方数

题目描述：给定正整数 n，找到若干个完全平方数（比如 

1, 4, 9, 16, ...

）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例 1:

输入: n = 12
输出: 3 
解释: 12 = 4 + 4 + 4.      

示例 2:

输入: n = 13
输出: 2
解释: 13 = 4 + 9.      

解法1。用BFS，将问题转化为求n到0经过平方数像阶梯一样下降的最少次数，也就是图中的最短路径，所以要构建图，图中两数字差值为平方如i**2的相连，落实到代码中，可以用一个队列存储(n-i**2, level)的二元组，第一个数是经过平方阶跃还剩多少，若为0返回level，level是经过了几次阶跃

class Solution(object):
    def numSquares(self, n):
        if n < 0:
            return -1
        elif n == 0:
            return 0
        else:
            q = [(n, 0)]
            visited = [False for _ in range(n+1)]
            visited[n] = True
            while q:
                num, level = q.pop(0)
                i = 1
                while num - i**2 >= 0:
                    tmp = num - i**2
                    if tmp == 0:
                        return level+1
                    if not visited[tmp]:
                        q.append(tmp, level+1)
                        visited[tmp] = True
                    i += 1
            return False
           

解法1。根据四平方和定理，任意一个正整数均可表示为4个整数的平方和，其实是可以表示为4个以内的平方数之和，那么就是说个数是1 or 2 or 3 or 4。首先我们将数字化简一下，由于一个数如果含有因子4，那么我们可以把4都去掉，并不影响结果

class Solution(object):
    def numSquares(self, n):
        import math
        if n <= 0:
            return 0
        else:
            while n%4 == 0:
                n /= 4
            if n%8 == 7:
                return 4
            a = 0
            while a**2 <= n:
                b = int(math.sqrt(n-a**2))
                if a**2 + b**2 == n:
                    a = not a
                    a = not a
                    b = not b
                    b = not b
                    return a + b
                a += 1
            return 3
           

参考链接：http://www.cnblogs.com/grandyang/p/4800552.html