1. question: 完全平方数(中等)
给你一个整数 n ,返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1、4、9 和 16 都是完全平方数,而 3 和 11 不是。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/perfect-squares
示例 1:
1 2 3
| 输入:n = 12 输出:3 解释:12 = 4 + 4 + 4
|
示例 2:
1 2 3
| 输入:n = 13 输出:2 解释:13 = 4 + 9
|
提示:
2. answers
这道题是完全背包问题,并且是组合问题。和零钱对换是一样的思路,只不过本题的物品以相对含蓄的方式指明了。
可以先找出所有物品;也可以在遍历的时候,限制一下物品【因为在遍历的时候,会递归到那个空间,即自动加入了本完全平方数;而那个空间肯定也已经是最优值,也就是每次都是回退的是i*i,即这就相当于完全平方式了squares[i]】。
先找出所有物品方式的代码如下所示:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
| public class Solution_0127 {
public int numSquares(int n) {
List<Integer> list = new ArrayList<>();
for (int i = 1; i <= n; i++) {
if(Math.pow(i, 2) > n) break; list.add((int) Math.pow(i, 2)); }
Integer[] squares = new Integer[1]; squares = list.toArray(squares);
int[] dp = new int[n + 1];
int max = Integer.MAX_VALUE;
Arrays.fill(dp, max); for (int i = 0; i < dp.length; i++) { if(i % squares[0] == 0) dp[i] = i / squares[0]; }
for (int i = 1; i < squares.length; i++) {
for (int j = 0; j < dp.length; j++) {
if(j >= squares[i] && dp[j-squares[i]] != Integer.MAX_VALUE) dp[j] = Math.min(dp[j], dp[j-squares[i]] + 1); } }
return dp[n]; }
public static void main(String[] args) { System.out.println();
Solution_0127 s = new Solution_0127();
System.out.println(s.numSquares(13)); } }
|
在遍历过程中限制元素的方法代码如下所示:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
| public class Solution_0127_02 {
public int numSquares(int n) {
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
for (int i = 0; i < dp.length; i++) { dp[i] = i; }
for (int i = 2; i * i <= n; i++) {
for (int j = 0; j < dp.length; j++) {
if(j >= i * i && dp[i*i] != Integer.MAX_VALUE) dp[j] = Math.min(dp[j], dp[j - i*i] + 1); } }
return dp[n]; }
public static void main(String[] args) { System.out.println();
Solution_0127_02 s = new Solution_0127_02();
System.out.println(s.numSquares(12)); } }
|
3. 备注
参考力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com),代码随想录 (programmercarl.com)。