0279. 完全平方数

0279. 完全平方数 #

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

题目大意 #

给定一个正整数 n,找到若干个完全平方数(比如 1,4,9,16,…),使得它们的和等于 n。要求返回和为 n 的完全平方数的最小数量。

解题思路 #

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

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

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

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

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

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

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

首先,我们将小于 n 的平方数放入数组中。然后使用「广度优先搜索」的方式,每次从当前节点值减去一个平方数,将减完的数加入队列。

  • 如果此时的数等于 0,则满足题意,返回层数。
  • 如果此时的数不等于 0,则将其加入队列,继续查找。

但是还有个问题:如何减少重复计算的次数。

我们可以使用一个 set 集合,来消除同一层中相同的数,这样就减少了计算次数。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def numSquares(self, n: int) -> int:
        if n == 0:
            return 0
        queue = collections.deque([n])
        visited = set()
        level = 0
        while queue:
            level += 1
            size = len(queue)
            for _ in range(size):
                top = queue.pop()
                for i in range(1, int(math.sqrt(top)) + 1):
                    x = top - i * i
                    if x == 0:
                        return level
                    if x not in visited:
                        queue.appendleft(x)
                        visited.add(x)
本站总访问量  次  |  您是本站第  位访问者