当前位置：首页 > article >正文

LeetCode题练习与总结：完全平方数--279

article 2024/10/6 18:18:24

一、题目描述

给你一个整数 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 <= 10^4

二、解题思路

这是一个典型的动态规划问题。我们可以使用一个数组 dp 来保存到每个数 i 的最少的完全平方数数量。对于每个数 i，我们需要考虑所有小于等于 i 的完全平方数 jj（其中 jj <= i），然后找出 dp[i - j*j] + 1 的最小值。

以下是具体的步骤：

初始化一个长度为 n+1 的数组 dp，所有元素初始化为最大值（比如 Integer.MAX_VALUE），因为我们要找最小值。
dp[0] 应该初始化为 0，因为 0 可以由 0 个完全平方数组成。
对于每个数 i（从 1 到 n），我们需要检查所有可能的完全平方数 jj（其中 jj <= i）。
对于每个 jj，我们将 dp[i] 更新为 min(dp[i], dp[i - jj] + 1)。
最终，dp[n] 就是我们要求的答案。

三、具体代码

class Solution {
    public int numSquares(int n) {
        // dp[i] 表示和为 i 的完全平方数的最少数量
        int[] dp = new int[n + 1];
        // 初始化 dp 数组
        Arrays.fill(dp, Integer.MAX_VALUE);
        // 0 可以由 0 个完全平方数组成
        dp[0] = 0;
        
        // 计算每个数的最少完全平方数数量
        for (int i = 1; i <= n; i++) {
            // 检查所有可能的完全平方数 j*j
            for (int j = 1; j * j <= i; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
        
        // 返回和为 n 的完全平方数的最少数量
        return dp[n];
    }
}

四、时间复杂度和空间复杂度

1. 时间复杂度

初始化 dp 数组的时间复杂度为 O(n)，因为我们需要对 n+1 个元素进行填充操作。
外层循环 for (int i = 1; i <= n; i++) 运行 n 次，因为它遍历了从 1 到 n 的每一个整数。
内层循环 for (int j = 1; j * j <= i; j++) 的运行次数依赖于 i 的值。对于每个 i，j 的最大值为 sqrt(i)，因此内层循环的运行次数随着 i 的增加而减少。
当 i 较小时，sqrt(i) 接近 i，内层循环接近 i 次；当 i 较大时，sqrt(i) 接近 sqrt(n)，内层循环接近 sqrt(n) 次。
平均来看，内层循环的运行次数大约为 sqrt(i)，所以我们可以将内层循环的总运行次数估计为所有 i 的 sqrt(i) 之和，即 sqrt(1) + sqrt(2) + … + sqrt(n)。由于 sqrt(i) 是一个递增函数，我们可以将其总和估计为小于 n * sqrt(n)。

因此，总的时间复杂度为 O(n) + O(n * sqrt(n))，简化后为 O(n * sqrt(n))。

2. 空间复杂度

dp 数组的大小为 n+1，因此需要 O(n) 的空间来存储所有的 dp 值。
除了 dp 数组外，代码中没有使用额外的空间，所有的变量都是常数级别的空间。

因此，总的空间复杂度为 O(n)。

五、总结知识点

动态规划 (Dynamic Programming, DP):
- 动态规划是一种算法设计技术，用于求解具有重叠子问题和最优子结构的问题。
- dp 数组用于存储子问题的解，避免重复计算。
数组的初始化:
- 使用 new int[n + 1] 创建一个整型数组 dp，其长度为 n + 1。
- 使用 Arrays.fill(dp, Integer.MAX_VALUE) 初始化数组 dp 的所有元素为 Integer.MAX_VALUE，表示初始时没有找到解。
基础循环结构:
- 两个嵌套的 for 循环用于遍历所有可能的数和它们的完全平方数。
数学运算:
- 使用 j * j 计算完全平方数。
- 使用 Math.min 函数来找出当前问题的最小解。
数组的索引操作:
- 通过索引 i 和 i - j * j 访问和更新 dp 数组。
递推关系:
- dp[i] = Math.min(dp[i], dp[i - j * j] + 1) 表示状态转移方程，用于更新 dp[i] 为最小的完全平方数数量。