0279. 完全平方数

0279. 完全平方数 #

  • 标签:广度优先搜索、数学、动态规划
  • 难度:中等

题目大意 #

描述:给定一个正整数 n。从中找到若干个完全平方数(比如 14116 …),使得它们的和等于 n

要求:返回和为 n 的完全平方数的最小数量。

说明

  • $1 \le n \le 10^4$。

示例

1
2
3
4
5
6
7
8
输入n = 12
输出3 
解释12 = 4 + 4 + 4


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

解题思路 #

暴力枚举思路:对于小于 n 的完全平方数,直接暴力枚举所有可能的组合,并且找到平方数个数最小的一个。

并且对于所有小于 $n$ 的完全平方数($k = 1, 4, 9, 16, …$),存在公式:$ans(n) = min(ans(n - k) + 1),k = 1,4,9,16,…$

即: n 的完全平方数的最小数量 == n - k 的完全平方数的最小数量 + 1

我们可以使用递归解决这个问题。但是因为重复计算了中间解,会产生堆栈溢出。

那怎么解决重复计算问题和避免堆栈溢出?

我们可以转换一下思维。

  1. n 作为根节点,构建一棵多叉数。
  2. n 节点出发,如果一个小于 n 的数刚好与 n 相差一个平方数,则以该数为值构造一个节点,与 n 相连。

那么求解和为 n 的完全平方数的最小数量就变成了求解这棵树从根节点 n 到节点 0 的最短路径,或者说树的最小深度。

这个过程可以通过广度优先搜索来做。

思路 1:广度优先搜索 #

  1. 定义 visited 为标记访问节点的 set 集合变量,避免重复计算。定义 queue 为存放节点的队列。使用 count 表示为树的最小深度,也就是和为 n 的完全平方数的最小数量。
  2. 首先,我们将 n 标记为已访问,即 visited.add(n)。并将其加入队列 queue 中,即 queue.append(n)
  3. count1,表示最小深度加 1。然后依次将队列中的节点值取出。
  4. 对于取出的节点值 value,遍历可能出现的平方数(即遍历 $[1, \sqrt{value} + 1]$ 中的数)。
  5. 每次从当前节点值减去一个平方数,并将减完的数加入队列。
    1. 如果此时的数等于 0,则满足题意,返回当前树的最小深度。
    2. 如果此时的数不等于 0,则将其加入队列,继续查找。

思路 1:代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def numSquares(self, n: int) -> int:
        if n == 0:
            return 0
        
        visited = set()
        queue = collections.deque([])
        
        visited.add(n)
        queue.append(n)
        
        count = 0
        while queue:
            // 最少步数
            count += 1
            size = len(queue)
            for _ in range(size):
                value = queue.pop()
                for i in range(1, int(math.sqrt(value)) + 1):
                    x = value - i * i
                    if x == 0:
                        return count
                    if x not in visited:
                        queue.appendleft(x)
                        visited.add(x)

思路 1:复杂度分析 #

  • 时间复杂度:$O(n \times \sqrt{n})$。
  • 空间复杂度:$O(n)$。
本站总访问量  次  |  您是本站第  位访问者