class Solution {
public:
int numSquares(int n) {
}
};
279. 完全平方数
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：
输入：n =12输出：3 解释：12 = 4 + 4 + 4
示例 2：
输入：n =13输出：2 解释：13 = 4 + 9
提示：
1 <= n <= 104原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2022-08-25 15:44:05
// 判断是否为完全平方数
func isPerfectSquare(x int) bool {
y := int(math.Sqrt(float64(x)))
return y*y == x
}
// 判断是否能表示为 4^k*(8m+7)
func checkAnswer4(x int) bool {
for x%4 == 0 {
x /= 4
}
return x%8 == 7
}
func numSquares(n int) int {
if isPerfectSquare(n) {
return 1
}
if checkAnswer4(n) {
return 4
}
for i := 1; i*i <= n; i++ {
j := n - i*i
if isPerfectSquare(j) {
return 2
}
}
return 3
}
golang 解法, 执行用时: 20 ms, 内存消耗: 6.1 MB, 提交时间: 2022-08-25 15:43:31
// 动态规划
func numSquares(n int) int {
f := make([]int, n+1)
for i := 1; i <= n; i++ {
minn := math.MaxInt32
for j := 1; j*j <= i; j++ {
minn = min(minn, f[i-j*j])
}
f[i] = minn + 1
}
return f[n]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}