Leecode #239 完全平方数

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

示例

示例 1:

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

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

解题思路

dfs和bfs两种，针对这题bfs速度更快不过耗费更多内存

class Solution:
    def numSquares(self, n: int) -> int:
        arr = [x**2 for x in range(int(n**0.5), 0, -1)]
        
        global count
        count = 10000
        def dfs(arr, begin, target, num):
            global count
            if num >= count:
                return
            if target == 0:
                count = num
            for i in range(begin, len(arr)):
                if arr[i] <= target:
                    dfs(arr, i, target-arr[i], num+1)
        dfs(arr, 0, n, 0)
        return count
    
    def numSquares(self, n: int) -> int:
        import collections
        arr = [x**2 for x in range(int(n**0.5), 0, -1)]
        
        global dq
        dq = collections.deque([n])
        
        count = 0
        while True:
            l = len(dq)
            for i in range(l):
                value = dq.pop()
                for j in arr:
                    temp = value - j
                    if temp >0:
                        dq.appendleft(temp)
                    elif temp == 0:
                        return count + 1
            count += 1

还有拉格朗日四平方和定理。。只能看看膜一下

class Solution:
    def isSquare(self, n: int) -> bool:
        sq = int(math.sqrt(n))
        return sq * sq == n

    def numSquares(self, n: int) -> int:
        # Lagrange's four-square theorem
        if self.isSquare(n):
            return 1
        while (n & 3) == 0:
            n >>= 2
        if (n & 7) == 7:
            return 4
        sq = int(math.sqrt(n)) + 1
        for i in range(1, sq):
            if self.isSquare(n - i * i):
                return 2
        return 3