Java 题解 | #完全平方数的草料#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return int整型一维数组
     */
    public int[] numSquares (int n) {
        // write code here
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j * j <= i; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
        List<Integer> ansList = new ArrayList<>();
        while (n > 0) {
            for (int i = (int) Math.sqrt(n); i >= 1; i--) {
                if (dp[n - i * i] + 1 == dp[n] && n >= i * i) {
                    ansList.add(i * i);
                    n -= i * i;
                    break;
                }
            }
        }
        int[] ans = new int[ansList.size()];
        for (int i = 0; i < ansList.size(); i++) {
            ans[i] = ansList.get(i);
        }
        Arrays.sort(ans);
        return ans;
    }
}

编程语言是Java。

该题考察的知识点是动态规划

代码的文字解释如下：创建一个长度为n+1的数组dp，用来存储每个数字n的最小完全平方数数量。将dp初始化为整型最大值，表示暂时无法达到该数字。通过两层循环遍历每个数字i（从1到n），以及每个完全平方数j（从1开始不超过i的平方根），更新dp[i]的值为dp[i-j*j]+1和当前dp[i]的较小值。这样，dp[i]就表示了数字i所需的最小完全平方数数量。

定义一个列表ansList用于存储结果。在循环体内，通过逆向遍历平方根i（从n的平方根开始到1），找到满足条件dp[n-ii]+1==dp[n]的最大平方数ii，并将其加入ansList中。同时，将n减去i*i，继续循环找下一个满足条件的平方数。

将ansList转换为数组ans，并对其进行排序，然后返回结果ans。