Update 0279. 完全平方数.md

itcharge · itcharge · commit a7f465813a9d · 2022-09-15T16:50:50.000+08:00
diff --git a/Solutions/0279. 完全平方数.md b/Solutions/0279. 完全平方数.md
@@ -5,54 +5,90 @@
 
 ## 题目大意
 
-给定一个正整数 n，找到若干个完全平方数（比如 1，4，9，16，...），使得它们的和等于 n。要求返回和为 n 的完全平方数的最小数量。
+**描述**：给定一个正整数 `n`。从中找到若干个完全平方数（比如 `1`、`4`、`1`、`16` ...），使得它们的和等于 `n`。
+
+**要求**：返回和为 `n` 的完全平方数的最小数量。
+
+**说明**：
+
+- $1 \le n \le 10^4$。
+
+**示例**：
+
+```Python
+输入：n = 12
+输出：3 
+解释：12 = 4 + 4 + 4
+
+
+输入：n = 13
+输出：2
+解释：13 = 4 + 9
+```
 
 ## 解题思路
 
-对于小于 n 的完全平方数，直接暴力枚举所有可能的组合，并且找到平方数个数最小的一个。
+对于小于 `n` 的完全平方数，直接暴力枚举所有可能的组合，并且找到平方数个数最小的一个。
 
-并且对于所有小于 n 的完全平方数（k = 1，4，9，16，...），存在公式 $ans(n) = min(ans(n-k) + 1)，k = 1，4，9，16，...$
+并且对于所有小于 `n` 的完全平方数（`k = 1, 4, 9, 16, ...`），存在公式 $ans(n) = min(ans(n - k) + 1)，k = 1，4，9，16，...$
 
-即： **n 的完全平方数的最小数量** 等于 **n - k 的完全平方数的最小数量 + 1**。
+即： **n 的完全平方数的最小数量 == n - k 的完全平方数的最小数量 + 1**。
 
-可以转为递归解决这个问题。但是因为重复计算了中间解，会产生堆栈溢出。
+我们可以使用递归解决这个问题。但是因为重复计算了中间解，会产生堆栈溢出。
 
-怎么解决重复计算问题和避免堆栈溢出？
+那怎么解决重复计算问题和避免堆栈溢出？
 
-将 n 作为根节点，构建一棵多叉数。从 n 节点出发，如果一个小于 n 的数刚好与 n 相差一个平方数，则以该数为值构造一个节点，与 n 相连。
+我们可转换一下思维。
 
-那么求解和为 n 的完全平方数的最小数量就变成了求解这棵树从 n 节点到 0 节点的最短路径，或者说数的最小深度。
+1. 将 `n` 作为根节点，构建一棵多叉数。
+2. 从 `n` 节点出发，如果一个小于 `n` 的数刚好与 `n` 相差一个平方数，则以该数为值构造一个节点，与 `n` 相连。
 
-首先，我们将小于 n 的平方数放入数组中。然后使用「广度优先搜索」的方式，每次从当前节点值减去一个平方数，将减完的数加入队列。
+那么求解和为 `n` 的完全平方数的最小数量就变成了求解这棵树从 `n` 节点到 `0` 节点的最短路径，或者说数的最小深度。
 
-- 如果此时的数等于 0，则满足题意，返回层数。
-- 如果此时的数不等于 0，则将其加入队列，继续查找。
+这个过程可以通过广度优先搜索来做。
 
-但是还有个问题：如何减少重复计算的次数。
+### 思路 1：广度优先搜索
 
-我们可以使用一个 set 集合，来消除同一层中相同的数，这样就减少了计算次数。
+1. 定义 `visited` 为标记访问节点的 set 集合变量，避免重复计算。定义 `queue` 为存放节点的队列。使用 `count` 表示和为 `n` 的完全平方数的最小数量。
+2. 首先，我们将 `n` 标记为已访问，即 `visited.add(n)`。并将其加入队列 `queue` 中，即 `queue.append(n)`。
+3. 令 `count` 加 `1`，表示最小深度加 `1`。然后依次将队列中的节点值取出。
+4. 对于取出的节点值 `value`，遍历可能出现的平方数（即遍历 $[1, \sqrt{value} + 1]$ 中的数）。
+5. 每次从当前节点值减去一个平方数，并将减完的数加入队列。
+   1. 如果此时的数等于 `0`，则满足题意，返回层数。
+   2. 如果此时的数不等于 `0`，则将其加入队列，继续查找。
 
-## 代码
+### 思路 1：代码
 
 ```Python
 class Solution:
     def numSquares(self, n: int) -> int:
         if n == 0:
             return 0
-        queue = collections.deque([n])
+        
         visited = set()
-        level = 0
+        queue = collections.deque([])
+        
+        visited.add(n)
+        queue.append(n)
+        
+        count = 0
         while queue:
-            level += 1
+            // 最少步数
+            count += 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
+                value = queue.pop()
+                for i in range(1, int(math.sqrt(value)) + 1):
+                    x = value - i * i
                     if x == 0:
-                        return level
+                        return count
                     if x not in visited:
                         queue.appendleft(x)
                         visited.add(x)
 ```
 
+### 思路 1：复杂度分析
+
+- **时间复杂度**：$O(n \times \sqrt{n})$。
+- **空间复杂度**：$O(n)$。
+
