Description

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Example 1:

Input: n = 12
Output: 3 
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

Solutions

  题意很简明,找到加和为 n 的最小个数的完全平方数,如 1,4,6,16 等。

1. DP

  面试中遇到过的题目,当场只给出了思路,还不对,要继续加油啊!查看了下前辈的思路,用动规来做,我们定义 dp[i] 为整数 i 最少能分解成多少个正整数的平方和

dp[i + j * j] = min(dp[i + j * j], dp[i] + 1)

  参考下得到这样的结果,也是对照之后才写出来的,还得注意:

# Time: O(n^2)
# Space: O(n)
class Solution:
    def numSquares(self, n: int) -> int:
        if n <= 0 :
            return 0
        dp = [float('inf')] * (n + 1)
        dp[0] = 0
        for i in range(1, n+1):
            j = 1
            while j * j <= n:
                dp[i] = min(dp[i], dp[i - j * j] + 1)
                j += 1
        return dp[n]

  之前 DP 这种解法还行,现在可能改了测试样例,会超时。要先计算得到所有的平方数:

class Solution:
   def numSquares(self, n: int) -> int:
        square_nums = [i**2 for i in range(0, int(n ** 0.5)+1)]
        
        dp = [float('inf')] * (n+1)
        # bottom case
        dp[0] = 0
        
        for i in range(1, n+1):
            for square in square_nums:
                if i < square:
                    break
                dp[i] = min(dp[i], dp[i-square] + 1)
        
        return dp[-1]
# 588/588 cases passed (4584 ms)
# Your runtime beats 36.9 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.9 MB)

2. 四平方定理

  参考 submit 的结果看到原来有四平方定理:

class Solution:
    def numSquares(self, n: int) -> int:
        '''
        思路:四平方定理(任何一个整数都可以表示成四个数的平方和)
        1.由于一个数如果含有因子4,那么我们可以把4都去掉,并不影响结果
        2.等于4的情况:如果一个数除以8余7的话,那么肯定是由4个完全平方数组成
        3.等于2或者1的情况:如果一个数由2个平方数组成,如果其中一个平方数是0,那么就是1,如果不是0,那就是2。
        4.等于3的情况:其他
        '''
        if n <= 0:
            return 1
        
        while n % 4 == 0:
            n = n / 4
        # 等于4的情况
        if n % 8 == 7:
            return 4
        
        i = 0
        while i * i <= n:
            j = int((n - i * i) ** 0.5)
            if i * i + j * j == n:
                if i == 0 or j == 0:
                    return 1
                else:
                    return 2
            i = i + 1
        return 3

# 588/588 cases passed (28 ms)
# Your runtime beats 99.54 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.8 MB)

References

  1. 279. Perfect Squares