第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
0279. 完全平方数

题目地址(279. 完全平方数)

题目描述

1
给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, ...)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
2
3
示例 1:
4
5
输入: n = 12
6
输出: 3
7
解释: 12 = 4 + 4 + 4.
8
示例 2:
9
10
输入: n = 13
11
输出: 2
12
解释: 13 = 4 + 9.
Copied!

前置知识

  • 递归
  • 动态规划

公司

  • 阿里
  • 百度
  • 字节

思路

直接递归处理即可,但是这种暴力的解法很容易超时。如果你把递归的过程化成一棵树的话(其实就是递归树), 可以看出中间有很多重复的计算。
如果能将重复的计算缓存下来,说不定能够解决时间复杂度太高的问题。
递归对内存的要求也很高, 如果数字非常大,也会面临爆栈的风险,将递归转化为循环可以解决。
递归 + 缓存的方式代码如下:
1
const mapper = {};
2
3
function d(n, level) {
4
if (n === 0) return level;
5
6
let i = 1;
7
const arr = [];
8
9
while (n - i * i >= 0) {
10
const hit = mapper[n - i * i];
11
if (hit) {
12
arr.push(hit + level);
13
} else {
14
const depth = d(n - i * i, level + 1) - level;
15
mapper[n - i * i] = depth;
16
arr.push(depth + level);
17
}
18
i++;
19
}
20
21
return Math.min(...arr);
22
}
23
/**
24
* @param {number} n
25
* @return {number}
26
*/
27
var numSquares = function (n) {
28
return d(n, 0);
29
};
Copied!
如果使用 DP,其实本质上和递归 + 缓存 差不多。
DP 的代码见代码区。

关键点解析

  • 如果用递归 + 缓存, 缓存的设计很重要 我的做法是 key 就是 n,value 是以 n 为起点,到达底端的深度。 下次取出缓存的时候用当前的 level + 存的深度 就是我们想要的 level.
  • 使用动态规划的核心点还是选和不选的问题
1
for (let i = 1; i <= n; i++) {
2
for (let j = 1; j * j <= i; j++) {
3
// 不选(dp[i]) 还是 选(dp[i - j * j])
4
dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
5
}
6
}
Copied!

代码

代码支持:CPP,JS
CPP Code:
1
class Solution {
2
public:
3
int numSquares(int n) {
4
static vector<int> dp{0};
5
while (dp.size() <= n) {
6
int m = dp.size(), minVal = INT_MAX;
7
for (int i = 1; i * i <= m; ++i) minVal = min(minVal, 1 + dp[m - i * i]);
8
dp.push_back(minVal);
9
}
10
return dp[n];
11
}
12
};
Copied!
JS Code:
1
/**
2
* @param {number} n
3
* @return {number}
4
*/
5
var numSquares = function (n) {
6
if (n <= 0) {
7
return 0;
8
}
9
10
const dp = Array(n + 1).fill(Number.MAX_VALUE);
11
dp[0] = 0;
12
for (let i = 1; i <= n; i++) {
13
for (let j = 1; j * j <= i; j++) {
14
// 不选(dp[i]) 还是 选(dp[i - j * j])
15
dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
16
}
17
}
18
19
return dp[n];
20
};
Copied!
复杂度分析
  • 时间复杂度:$O(N^2)$
  • 空间复杂度:$O(N)$
大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。