无锡网站制作方案,网站备案要注意什么,手机软件开发公司排名,免费个人域名邮箱题目
完全平方数 给你一个整数 n #xff0c;返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数#xff0c;其值等于另一个整数的平方#xff1b;换句话说#xff0c;其值等于一个整数自乘的积。例如#xff0c;1、4、9 和 16 都是完全平方数#xff0c;而…题目
完全平方数 给你一个整数 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;}
}
