快速求解完全平方数的最少数量

LeetCode279给你一个整数n返回和为n的完全平方数的最少数量。完全平方数是一个整数其值等于另一个整数的平方换句话说其值等于一个整数自乘的积。例如1、4、9和16都是完全平方数而3和11不是。示例 1输入n 12输出3解释12 4 4 4示例 2输入n 13输出2解释13 4 9Python解法1.BFSfrom 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*(8m7) 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 个平方数凑出来当且仅当它满足形式\(n4^k \times (8m7)\) 这种数必须恰好 4 个平方数相加没有更少方案直接返回 4。Java解法1.BFSimport java.util.HashSet; import java.util.LinkedList; import java.util.Queue; class Solution { public int numSquares(int n) { HashSetInteger visited new HashSet(); Queueint[] 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*(8m7) 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_setint visited; queuepairint, 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; } };