网站二级页面需不需要设置关键词我要自学网网站
题目
完全平方数
给你一个整数 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
题解
记忆化搜索
class Solution {private int[][] cache;public int numSquares(int n) {// if (n == 1) {// return 1;// }int len = (int) Math.sqrt(n);cache = new int[len][n + 1];for (int i = 0; i < len; i++) {Arrays.fill(cache[i],-1);}int ans = dfs(len - 1, n);return ans < Integer.MAX_VALUE / 2 ? ans : -1;}public int dfs(int i, int c) {if (i < 0) {return c == 0 ? 0 : Integer.MAX_VALUE / 2;}if (cache[i][c] != -1) {return cache[i][c];}if (c < (i + 1) * (i + 1)) {return cache[i][c] = dfs(i - 1, c);}return cache[i][c] = Math.min(dfs(i - 1, c), dfs(i, c - (i + 1) * (i + 1)) + 1);}
}
递推
class Solution {public int numSquares(int n) {int len = (int)Math.sqrt(n);int[][] f = new int[2][n + 1];Arrays.fill(f[0], Integer.MAX_VALUE / 2);f[0][0] = 0;for (int i = 0; i < len; i++) {for (int c = 1; c <= n; c++) {if (c < (i + 1) * (i + 1)) {f[(i + 1)%2][c] = f[i%2][c];} else {f[(i + 1)%2][c] = Math.min(f[i%2][c],f[(i + 1)%2][c - (i + 1) * (i + 1)] + 1);}}}int ans = f[len%2][n];return ans < Integer.MAX_VALUE / 2 ? ans : -1;}
}
两个数组优化
class Solution {public int numSquares(int n) {int len = (int)Math.sqrt(n);int[][] f = new int[2][n + 1];Arrays.fill(f[0], Integer.MAX_VALUE / 2);f[0][0] = 0;for (int i = 0; i < len; i++) {for (int c = 1; c <= n; c++) {if (c < (i + 1) * (i + 1)) {f[(i + 1)%2][c] = f[i%2][c];} else {f[(i + 1)%2][c] = Math.min(f[i%2][c],f[(i + 1)%2][c - (i + 1) * (i + 1)] + 1);}}}int ans = f[len%2][n];return ans < Integer.MAX_VALUE / 2 ? ans : -1;}
}
一个数组优化
class Solution {public int numSquares(int n) {int len = (int)Math.sqrt(n);int[] f = new int[n + 1];Arrays.fill(f, Integer.MAX_VALUE / 2);f[0] = 0;for (int i = 0; i < len; i++) {for (int c = (i + 1) * (i + 1); c <= n; c++) {f[c] = Math.min(f[c],f[c - (i + 1) * (i + 1)] + 1);}}int ans = f[n];return ans < Integer.MAX_VALUE / 2 ? ans : -1;}
}