海丰建设局网站,做详情页比较好的网站,做网站找哪个部门,室内设计培训学校哪个好Problem: 279. 完全平方数 文章目录 思路#x1f496; 完全背包#x1f496; 滚动数组优化#x1f496; 四平方和定理 思路
#x1f468;#x1f3eb; 三叶神解
#x1f468;#x1f3eb; 数学解法
#x1f496; 完全背包
⏰ 时间复杂度: O ( n 2 n ) O(n^2 … Problem: 279. 完全平方数 文章目录 思路 完全背包 滚动数组优化 四平方和定理 思路
三叶神解
数学解法 完全背包
⏰ 时间复杂度: O ( n 2 n ) O(n^2 \sqrt{n}) O(n2n )
class Solution {int INF 0x3f3f3f3f;public int numSquares(int n){ListInteger list new ArrayList();int t 1;while (t * t n){list.add(t * t);t;}int m list.size();int[][] f new int[m 1][n 1];// f[i][j] 表示考虑前 i 个物品凑出 j 所使用的最小元素个数Arrays.fill(f[0], INF);// 在 0 个物品中选除了价值 0 外都是非法情况f[0][0] 0;for (int i 1; i m; i){int x list.get(i - 1);// x 表示当前物品的 价值for (int j 0; j n; j){f[i][j] f[i - 1][j];// 不选当前物品for (int k 1; k * x j; k)// 选取 k 个当前物品if (f[i - 1][j - k * x] ! INF)f[i][j] Math.min(f[i][j], f[i - 1][j - k * x] k);}}return f[m][n];}
}滚动数组优化
⏰ 时间复杂度: O ( n n ) O(n\sqrt{n}) O(nn )
class Solution {public int numSquares(int n){int[] f new int[n 1];//f[i] 表示和为 i 的最小完全平方数和 的数量Arrays.fill(f, 0x3f3f3f3);f[0] 0;for (int t 1; t * t n; t){int x t * t;for (int j x; j n; j)f[j] Math.min(f[j], f[j - x] 1);}return f[n];}
}四平方和定理
class Solution {public int numSquares(int n) {//判断是否是 1if (isSquare(n)) {return 1;}//判断是否是 4int temp n;while (temp % 4 0) {temp / 4;}if (temp % 8 7) {return 4;}//判断是否是 2for (int i 1; i * i n; i) {if (isSquare(n - i * i)) {return 2;}}return 3;}//判断是否是平方数private boolean isSquare(int n) {int sqrt (int) Math.sqrt(n);return sqrt * sqrt n;}
}
