210 - 279 完全平方数

题目

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

示例 1:

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

示例 2:

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

解答

开平方根，取地板，然后减掉这个数的平方。

动态规划

https://leetcode-cn.com/problems/perfect-squares/solution/hua-jie-suan-fa-279-wan-quan-ping-fang-shu-by-guan/

class Solution:
    def numSquares(self, n: int) -> int:
        if n == 0:
            return 0
        dp = [i for i in range(n+1)]
        for i in range(1, n+1):
            j = 1
            while i-j*j >= 0:
                dp[i] = min(dp[i], dp[i-j*j]+1)
                j += 1
        return dp[n]

Runtime: 6116 ms, faster than 12.00% of Python3 online submissions for Perfect Squares.

Memory Usage: 12.7 MB, less than 100.00% of Python3 online submissions for Perfect Squares.

四平方和定理

https://leetcode-cn.com/problems/perfect-squares/solution/bfs-dong-tai-gui-hua-shu-xue-by-powcai/

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

    def numSquares(self, n: int) -> int:
        import math
        if Solution.isSquare(self, 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

Runtime: 56 ms, faster than 97.07% of Python3 online submissions for Perfect Squares.

Memory Usage: 12.5 MB, less than 100.00% of Python3 online submissions for Perfect Squares.