Skip to content

279 perfect squares

279. Perfect Squares

难度: Medium

刷题内容

原题连接

  • https://leetcode.com/problems/perfect-squares
  • https://leetcode-cn.com/problems/perfect-squares

内容描述

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

示例 1:

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

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

解题方案

思路 1: 暴力破解

求某个数的最少平方加和的个数

1. diff集合(小到大排序) = n - 平方根的平方的集合
2. 每一层都在不断 - 平方根的平方
3. 直到出现 0 代表得到结果

当然，你可以提前: dp.append(count) => return count, 得到最小值

n = 15 的时候
    -9  -4  -1
>>> [6, 11, 14]
>>> [2, 5, 7, 10, 13]
>>> [1, 3, 4, 6, 9, 12]
>>> [0, 2, 3, 5, 8, 11]
>>> [1, 2, 4, 7, 10]
>>> [0, 1, 3, 6, 9]
>>> [0, 2, 5, 8]
>>> [1, 4, 7]
>>> [0, 3, 6]
>>> [2, 5]
>>> [1, 4]
>>> [0, 3]
>>> [2]
>>> [1]
>>> [0]
>>> []
4  ---  [4, 6, 7, 9, 12, 15]

class Solution(object):
    def numSquares(self, n: int) -> int:
        result = []
        count = 1
        diff_list = [n]
        while len(diff_list):
            diff_list = sorted(list(set([diff-i**2 for diff in diff_list for i in range(1, diff+1) if diff>=i**2])))
            # print(">>> %s" % diff_list)
            if len(diff_list) < 1:
                break 
            elif 0 in diff_list:
                result.append(count)
            count += 1
        # print(min(result), " --- ", result)
        return min(result) if len(result)>0 else -1

思路 2: 动态规划

1. 初始化 inf 从0开始，所以数组长度 n+1 
2. 考虑到是平方，意味着他的间隔可能是跳跃性的，所以 
        n  =   (n-j*j)  + j*j
        dp[i] = dp[i-1] + 1
3. 那么 min 就是未来找到最小值而存在的，因为需要遍历很多个平方， dp[i] 用户存储最小值
4. 返回 dp[-1] 的结果，也就是最终 n 的值

class Solution(object):
    def numSquares(self, n: int) -> int:
        square_nums = [i**2 for i in range(1, int(n**0.5)+1)]
        dp = [float('inf')] * (n+1)
        dp[0] = 0
        for i in range(1, n+1):
            for square in square_nums:
                if i < square:
                    break
                # print("%s --- %s结果需要一次 --- %s结果需要%s次" % (i, square, i-square, dp[i-square]))
                dp[i] = min(dp[i], dp[i-square] + 1)
        return dp[-1]

未测试

思路三：

还是慢，有个数学方法, runtime beats 98.48%

import math
class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        def isSquare(num):
            tmp = int(math.sqrt(num))
            return tmp * tmp == num
        while n & 3 == 0: # n % 4 == 0 
            n >>= 2
        if n & 7 == 7: # n % 8 == 7
            return 4
        if isSquare(n):
            return 1
        sqrt_n = int(math.sqrt(n))
        for i in range(1, sqrt_n + 1):
            if isSquare(n-i*i):
                return 2
        return 3

in order to understand, I suggest u read:

here is the Lagrange's Four Square theorem - Limit the result to <= 4:

And this article, in which you can also find the way to present a number as a sum of four squares:

回到顶部