LeetCode279
给你一个整数n，返回和为n的完全平方数的最少数量。
完全平方数是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9和16都是完全平方数，而3和11不是。
示例 1：
输入：n =12，输出：3
解释：12 = 4 + 4 + 4
示例 2：
输入：n =13，输出：2
解释：13 = 4 + 9
Python解法
1.BFS
from collections import deque class Solution: def numSquares(self, n: int) -> int: # 记录已经处理过的数字，避免重复入队，减少计算 visited = set() # 队列元素：(当前剩余数值, 当前已用平方数个数) q = deque() # 初始起点：数字n，使用0个平方数 q.append((n, 0)) visited.add(n) # 队列不为空就持续遍历每一层 while q: # 队首出队，处理当前层节点 cur, step = q.popleft() j = 1 # 枚举所有不大于cur的平方数 j² while j*j <= cur: next_val = cur - j*j # 刚好减到0，找到最少数量：当前step+本次用的1个平方数 if next_val == 0: return step + 1 # 没访问过才入队，防止重复循环 if next_val not in visited: visited.add(next_val) q.append((next_val, step + 1)) j += 1 return -12.数学方法
import math class Solution: def numSquares(self, n: int) -> int: # 判断完全平方数 def is_square(x): y = int(math.sqrt(x)) return y * y == x # 判断是否为4^k*(8m+7) def check_four(x): while x % 4 == 0: x //= 4 return x % 8 == 7 if is_square(n): return 1 if check_four(n): return 4 i = 1 while i * i <= n: rest = n - i*i if is_square(rest): return 2 i += 1 return 3解释（数学）
1. 拉格朗日四平方和定理
任意正整数，一定能写成最多 4 个完全平方数之和抖音百科。 也就是说，最坏情况只用 4 个，绝对不需要 5 个及以上，答案上限就是 4。
2. 勒让德三平方和定理（关键推论）
一个数不能只用 1、2、3 个平方数凑出来，当且仅当它满足形式：
\(n=4^k \times (8m+7)\) 这种数必须恰好 4 个平方数相加，没有更少方案，直接返回 4。
Java解法
1.BFS
import java.util.HashSet; import java.util.LinkedList; import java.util.Queue; class Solution { public int numSquares(int n) { HashSet<Integer> visited = new HashSet<>(); Queue<int[]> q = new LinkedList<>(); q.add(new int[]{n, 0}); visited.add(n); while (!q.isEmpty()) { int[] curPair = q.poll(); int cur = curPair[0]; int step = curPair[1]; int j = 1; while ((long) j * j <= cur) { int nextVal = cur - j * j; if (nextVal == 0) { return step + 1; } if (!visited.contains(nextVal)) { visited.add(nextVal); q.add(new int[]{nextVal, step + 1}); } j++; } } return -1; } }2.数学方法
class Solution { public int numSquares(int n) { if (isSquare(n)) return 1; if (checkFour(n)) return 4; for (int i = 1; i * i <= n; i++) { int rest = n - i * i; if (isSquare(rest)) return 2; } return 3; } // 判断完全平方数 private boolean isSquare(int x) { int y = (int) Math.sqrt(x); return y * y == x; } // 判断 n = 4^k*(8m+7) private boolean checkFour(int x) { while (x % 4 == 0) x /= 4; return x % 8 == 7; } }C++解法
1.BFS
#include <queue> #include <unordered_set> using namespace std; class Solution { public: int numSquares(int n) { unordered_set<int> visited; queue<pair<int, int>> q; q.push({n, 0}); visited.insert(n); while (!q.empty()) { auto [cur, step] = q.front(); q.pop(); int j = 1; while (1LL * j * j <= cur) { int nextVal = cur - j * j; if (nextVal == 0) { return step + 1; } if (!visited.count(nextVal)) { visited.insert(nextVal); q.push({nextVal, step + 1}); } j++; } } return -1; } };2.数学方法
#include <cmath> using namespace std; class Solution { public: int numSquares(int n) { if (isSquare(n)) return 1; if (checkFour(n)) return 4; for (int i = 1; 1LL * i * i <= n; ++i) { int rest = n - i * i; if (isSquare(rest)) return 2; } return 3; } private: bool isSquare(int x) { int y = sqrt(x); return y * y == x; } bool checkFour(int x) { while (x % 4 == 0) x /= 4; return x % 8 == 7; } };
