Daily LeetCode 279. Perfect Squares

上周有三门考试，刷题就停了一周，今天继续。

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

Medium

问题描述

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.

思路及代码

这一题要求一个数最少能拆分成几个完全平方数的和。

因为实在动态规划的问题列表里面刷的题，所以我就直接从动态规划入手解决这个问题了。维护一个长度为n+1的一维数组dp，dp[i]表示i最少能拆分成几个完全平方数的和，dp[0]初始化为0，其余位置初始化为sys.maxsize。用一个二重循环更新dp数组，dp[i + j * j] = min(dp[i + j * j], dp[i] + 1)，dp[n]即为我们要求的结果。

代码如下：

import sys

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

但是这种方法的时间复杂度很高，我在LeetCode的论坛看到了其它一些更好的方法：

数学方法

首先，我们需要了解四平方和定理，每个正整数都能够表示成四个整数的平方和，因此返回值只有可能有四种：1，2，3，4

当n是完全平方数时，返回值为1

当n能够写成$n=4^k\times (8 \times m +7)$的形式时，返回值为4

import math

class Solution:
    def numSquares(self, n: int) -> int:
        def is_square(n):
            sqrt_n = int(math.sqrt(n))
            return sqrt_n ** 2 == n

        if is_square(n):
            return 1

        while n & 3 == 0: #n%4==0
            n >>= 2
        if n & 7 == 7: #n%8 == 7
            return 4

        sqrt_n = int(math.sqrt(n))
        for i in range(1, sqrt_n + 1):
            if is_square(n - i * i):
                return 2

        return 3      

BFS

广度优先遍历的思想是将小于等于n的每个完全平方数都看作是图中的一个节点，当且仅当满足j = i + 完全平方数时，i节点与j节点相连。从0节点开始做广度优先遍历，当遍历到节点n时，说明我们遍历过的节点和为n，此时遍历步数就是最终结果。

大佬的代码如下：

class Solution:
    def numSquares(self, n: int) -> int:
        if n <= 0: return 0
        perfect_squres = [i ** 2 for i in range(1, int(n ** 0.5) + 1)]
        d, q, nq = 1, {n}, set()
        while q:
            for node in q:
                for square in perfect_squres:
                    if node == square: return d
                    if node < square: break
                    nq.add(node - square)
            d, q, nq = d + 1, nq, set()