05 August 2008
Given a positive integer n, find the least number of perfect square numbers (for example, 1
1, 4, 9, 16, ...
Example 1:
1
2
3
Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.
Example 2:
1
2
3
Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.
给一个正整数，求最少由几个完全平方数组成，考察四平方和定理（没听说过）。
如果是DP的办法，其中一个办法是建立一个一维数组， dp[i]表示组成i这个数字需要的最少的的平方数，DP方程为dp[i] = min(dp[i - x^2] + 1 for all x)，因为x有很多种选择，需要选一个最小的；初始化第一个值为0，在循环里计算选择x和不选择x，谁的次数少。
每次增加一个dp数组的长度，里面那个for循环一次循环结束就算好下一个数由几个完全平方数组成，直到增加到第n+1个，返回即可；
DP的效率不是很高， 一个更加高效的办法是，根据四平方和定理，任意一个正整数均可表示为4个整数的平方和（4个，3个，2个或者1个），首先将数字化简一下，由于一个数如果含有因子4，那么我们可以把4都去掉，并不影响结果，比如2和8,3和12等等，返回的结果是相同的。还有一个可以化简的地方就是，如果一个数除以8余7的话，那么这个数肯定是由4个完全平方数组成。经过两次化简，一个很大的数有可能就会变得很小了，大大减少了运算时间，接下来将化简后的数拆为两个平方数之和，如果拆成功了那么就会返回1或2，因为其中一个平方数可能为0. (由于输入的n是正整数，所以不存在两个平方数均为0的情况)，然后看a和b是否为正整数，都为正整数的话返回2，只有一个是正整数的话就返回1。
DP - 1，比较直观的做法，运行速度比较慢，因为这里Math.sqrt()的复杂度是Quisilinear O(logn)，时间复杂度O(n^2*logn)，可以查看Leetcode 69 - sqrt(x)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public int numSquares(int n) {
int[] dp = new int[n + 1];
Arrays.fill(dp, n);//dp[i]表示i这个数所需的最小平方数,最大不会超过n个
dp[0] = 0; //0不会被任何正整数的平方数构成
for (int i = 1; i <= n; i++) {
for (int x = 1; x <= Math.sqrt(i); x++) {
dp[i] = Math.min(dp[i], dp[i - x * x] + 1); //选x这个数和不选x这个数看谁少
}
}
return dp[n];
}
}
DP - 2，只改了下sqrt为乘法，时间复杂度O(n^2)，leetcode上运行速度快了很多
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public int numSquares(int n) {
int[] dp = new int[n + 1];
Arrays.fill(dp, n);//dp[i]表示i这个数所需的最小平方数,最大不会超过n个
dp[0] = 0; //0不会被任何正整数的平方数构成
for (int i = 1; i <= n; i++) {
for (int x = 1; x * x <= i; x++) {
dp[i] = Math.min(dp[i], dp[i - x * x] + 1); //选x这个数和不选x这个数看谁少
}
}
return dp[n];
}
}
四平方和的方法，时间复杂度O(n)，最快
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public int numSquares(int n) {
//两步化简
while (n % 4 == 0) n /= 4;
if (n % 8 == 7) return 4;
int a = -1, b = (int)Math.sqrt(n);
n -= b * b;
b += b + 1;
while (a <= b) {
if (n < 0) {
n += b -= 2;
} else if (n > 0) {
n -= a += 2;
} else {
return a < 0 ? 1 : 2;
}
}
return 3;
}
}