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

力扣最热一百题——完全平方数（中等难度，详细分析）

article 2024/11/15 15:04:35

目录

题目链接：279. 完全平方数 - 力扣（LeetCode）

题目描述

解法一：动态规划

思路分析：

代码解析：

代码流程：

示例：

Java写法：

C++写法：

运行时间

时间复杂度和空间复杂度

时间复杂度：

空间复杂度：

解法二：数学解法（来自官方）

实现思路     

代码的实现思路：

1. 完全平方数检查（isPerfectSquare(n)）

2. Lagrange 四平方和定理的应用（checkAnswer4(n)）

3. 两个完全平方数之和（通过遍历）

4. 返回 3

代码的整体流程：

Java写法：

C++写法：

运行时间

时间复杂度和空间复杂度

总结

方法一：动态规划

方法二：数学方法（四平方和定理）

总结

题目链接：279. 完全平方数 - 力扣（LeetCode）

注：下述题目描述和示例均来自力扣

题目描述

给你一个整数 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) 来求解问题。核心思想是：通过构建一个 dp 数组，dp[i] 表示构成数字 i 的最少完全平方数的个数。

代码解析：

  1. dp 数组的初始化：

    • dp[i] 表示构成整数 i 的最少完全平方数的个数。
    • 初始时，所有 dp[i] 都被设为 Integer.MAX_VALUE，表示还未计算过最小值。

  2. 动态规划的转移：

    • 对于每一个 i（从 1 到 n），我们考虑所有小于等于 i 的完全平方数。
    • 对于每个 j，如果 j * j <= i，则有一个子问题：dp[i - j * j]，即将当前问题转化为求解 i - j * j 的最少平方数。
    • dp[i] 取所有 dp[i - j * j] + 1 的最小值，表示当前 i 可以通过加上一个完全平方数 j * j 来构成。

  3. 结果：

    • 最终，dp[n] 即为要求的结果，它表示将 n 分解为完全平方数和所需的最小个数。

代码流程：

  1. 初始化一个大小为 n + 1 的 dp 数组。
  2. 遍历从 1 到 n，对每个 i，遍历所有小于等于 i 的完全平方数 j * j。
  3. 对于每个 i，更新 dp[i] 的值，取 dp[i - j * j] + 1 的最小值。
  4. 最终返回 dp[n]。

示例：

假设 n = 12，我们希望找到构成 12 的最少完全平方数的个数。

  • 完全平方数包括：1, 4, 9。
  • 通过动态规划，逐步计算出每个 dp[i]：
    • dp[12] 最终会等于 3，因为 12 = 4 + 4 + 4，即需要 3 个完全平方数（4）。

Java写法：

class Solution {
    public int numSquares(int n) {
        // 创建 dp 数组，用于存储每个数 i 所需的最少完全平方数个数
        // dp[i] 表示构成 i 的最少完全平方数的个数
        int[] dp = new int[n + 1];
        
        // 从 1 到 n 遍历，计算每个数 i 的最少完全平方数个数
        for (int i = 1; i <= n; i++) {
            // 初始值设为最大值，表示还没有计算出最小的完全平方数个数
            int Nmin = Integer.MAX_VALUE;
            
            // 遍历所有小于等于 i 的完全平方数 j*j
            for (int j = 1; j * j <= i; j++) {
                // 计算出 i 减去 j*j 后的结果 dp[i - j*j]
                // 并更新最小值 Nmin dp[i - j*j] 的最小值
                Nmin = Math.min(Nmin, dp[i - j * j]);
            }
            
            // 更新 dp[i]，最小值 + 1，因为当前 j*j 是加到结果中的一个完全平方数
            dp[i] = Nmin + 1;
        }
        
        // 返回 dp[n]，即 n 所需的最少完全平方数个数
        return dp[n];
    }
}

C++写法：

class Solution {
public:
    int numSquares(int n) {
        // 创建 dp 数组，用于存储每个数 i 所需的最少完全平方数个数
        vector<int> dp(n + 1, INT_MAX);
        
        // dp[0] = 0，因为 0 不需要任何完全平方数
        dp[0] = 0;
        
        // 从 1 到 n 遍历，计算每个数 i 的最少完全平方数个数
        for (int i = 1; i <= n; i++) {
            // 遍历所有小于等于 i 的完全平方数 j*j
            for (int j = 1; j * j <= i; j++) {
                // 计算出 i 减去 j*j 后的结果 dp[i - j*j]
                // 更新 dp[i]，最小值 + 1，因为当前 j*j 是加到结果中的一个完全平方数
                dp[i] = min(dp[i], dp[i - j * j] + 1);
            }
        }
        
        // 返回 dp[n]，即 n 所需的最少完全平方数个数
        return dp[n];
    }
};

  • C++ 中的 vector<int>：

    • 在 C++ 中，我们用 vector<int> 来代替 Java 中的数组。初始化时，vector<int> dp(n + 1, INT_MAX) 将 dp 数组的所有元素初始化为 INT_MAX，表示还没有计算过最小完全平方数个数。

  • INT_MAX 代替 Integer.MAX_VALUE：

    • C++ 中使用 INT_MAX 来表示一个足够大的整数，它相当于 Java 中的 Integer.MAX_VALUE。

  • min 函数：

    • C++ 使用 min() 函数来取两个数中的最小值，类似于 Java 中的 Math.min()。

  • 初始化 dp[0] = 0：

    • 在 Java 中，我们隐式地假设 dp[0] = 0，在 C++ 中我们显式地初始化 dp[0] = 0，因为 0 需要 0 个完全平方数。

运行时间

时间复杂度和空间复杂度

时间复杂度：

  • 外层循环：n 次（从 1 到 n）。
  • 内层循环：对于每个 i，最多遍历 sqrt(i) 个完全平方数。
  • 因此，时间复杂度为 O(n * sqrt(n))。

空间复杂度：

  • 使用一个大小为 n + 1 的数组 dp，因此空间复杂度为 O(n)。

解法二：数学解法（来自官方）

        四平方和定理（Four Square Theorem）是一个著名的数学定理，它描述了每个正整数都可以表示为最多四个完全平方数之和。更正式地说：

定理内容： 每个正整数 nnn 都可以表示为四个完全平方数之和，即：

n=x^1_2+x^2_2+x^3_2+x^4_2

其中，x_1,x_2,x_3,x_4是整数。

例如：

  • 7 = 4+1+1+1（即 2^2+1^2+1^2+1^2）
  • 12 = 9+1+1+1（即 3^2+1^2+1^2+1^2）

这个定理的数学证明最早由 Lagrange 在1770年提出。

实现思路     

        根据 Lagrange 四平方和定理 来求解一个整数 n 可以由多少个完全平方数（平方数是指某个整数的平方，如 1, 4, 9, 16 等）之和表示。具体来说，该代码的功能是返回整数 n 需要的最小完全平方数个数。这里的最小个数，可以是 1、2、3 或 4 个完全平方数之和。

代码的实现思路：

        为了高效地解决这个问题，代码主要基于以下几个步骤：

1. 完全平方数检查（isPerfectSquare(n)）

  • 在开始时，首先检查给定的 n 是否是完全平方数。如果是完全平方数（即存在某个整数 k，使得 k*k = n），那么直接返回 1，因为任何完全平方数都可以用一个完全平方数表示。

  • 判断方式：我们通过求 n 的平方根并检查其平方是否等于 n 来判断一个数是否为完全平方数。例如，如果 n = 4，则 sqrt(4) = 2，2 * 2 = 4，因此 n 是一个完全平方数。

2. Lagrange 四平方和定理的应用（checkAnswer4(n)）

  • 如果 n 不是完全平方数，接下来使用 Lagrange 四平方和定理 判断 n 是否符合 4^k * (8m + 7) 这种形式。根据该定理，如果一个数 n 能表示为 4^k * (8m + 7)（即经过若干次除以 4 后，得到的数是 7 mod 8），那么该数只能由 4 个完全平方数表示。

  • 判断方式：我们通过反复将 n 除以 4，直到不能再被 4 整除。然后检查结果是否符合 x % 8 == 7，如果是，则说明 n 可以由 4 个完全平方数之和表示。

3. 两个完全平方数之和（通过遍历）

  • 如果 n 既不是完全平方数，也不符合 4^k * (8m + 7) 的形式，接下来尝试通过两个完全平方数之和表示 n。这是通过遍历 1^2, 2^2, 3^2, ... 等平方数来进行的，检查 n - i^2 是否为完全平方数。

  • 判断方式：对每个 i 从 1 开始，检查 n - i*i 是否是完全平方数。如果是，则 n 可以表示为 i^2 + j^2，因此返回 2。

4. 返回 3
  • 如果以上所有方法都不能解决问题（即 n 不能由 1、2 或 4 个完全平方数表示），则根据 Lagrange 四平方和定理，n 至少可以通过 3 个完全平方数表示。因此，如果经过所有的检查后，仍然没有找到合适的表示方式，就返回 3。

代码的整体流程：

  1. 检查是否是完全平方数，如果是，直接返回 1。
  2. 检查是否符合 4^k * (8m + 7) 的形式，如果是，返回 4。
  3. 检查是否可以表示为两个完全平方数之和，如果是，返回 2。
  4. 如果都不满足，返回 3。

Java写法：

class Solution {
    public int numSquares(int n) {
        // 第一步：检查 n 是否是完全平方数
        if (isPerfectSquare(n)) {
            return 1;
        }
        
        // 第二步：检查是否符合 4^k * (8m + 7) 的形式
        if (checkAnswer4(n)) {
            return 4;
        }
        
        // 第三步：检查是否能表示为两个完全平方数之和
        for (int i = 1; i * i <= n; i++) {
            int j = n - i * i;
            if (isPerfectSquare(j)) {
                return 2;
            }
        }
        
        // 第四步：如果以上都不满足，则返回 3
        return 3;
    }

    // 判断 n 是否为完全平方数
    public boolean isPerfectSquare(int x) {
        int y = (int) Math.sqrt(x);  // 计算 x 的平方根
        return y * y == x;  // 如果平方根的平方等于 x，则说明是完全平方数
    }

    // 判断 n 是否符合 4^k * (8m + 7) 的形式
    public boolean checkAnswer4(int x) {
        // 判断 x 是否符合 4^k * (8m + 7) 的形式
        while (x % 4 == 0) {
            x /= 4;  // 一直除以 4，直到不能再除
        }
        return x % 8 == 7;  // 如果除以 4 后剩下的 x 是 7 mod 8，则符合该形式
    }
}

C++写法：

#include <cmath>
using namespace std;

class Solution {
public:
    int numSquares(int n) {
        // 第一步：检查 n 是否是完全平方数
        if (isPerfectSquare(n)) {
            return 1;
        }
        
        // 第二步：检查是否符合 4^k * (8m + 7) 的形式
        if (checkAnswer4(n)) {
            return 4;
        }
        
        // 第三步：检查是否能表示为两个完全平方数之和
        for (int i = 1; i * i <= n; i++) {
            int j = n - i * i;
            if (isPerfectSquare(j)) {
                return 2;
            }
        }
        
        // 第四步：如果以上都不满足，则返回 3
        return 3;
    }

private:
    // 判断 n 是否为完全平方数
    bool isPerfectSquare(int x) {
        int y = static_cast<int>(sqrt(x));  // 计算 x 的平方根
        return y * y == x;  // 如果平方根的平方等于 x，则说明是完全平方数
    }

    // 判断 n 是否符合 4^k * (8m + 7) 的形式
    bool checkAnswer4(int x) {
        // 判断 x 是否符合 4^k * (8m + 7) 的形式
        while (x % 4 == 0) {
            x /= 4;  // 一直除以 4，直到不能再除
        }
        return x % 8 == 7;  // 如果除以 4 后剩下的 x 是 7 mod 8，则符合该形式
    }
};

运行时间

时间复杂度和空间复杂度

  • 时间复杂度： O(\sqrt{n})。
  • 空间复杂度： O(1)。

总结

        通过 动态规划 和 数学方法 两种不同的方式来解决求解一个整数 n 需要多少个完全平方数之和的问题。文章详细介绍了每种方法的思路、代码实现以及时间和空间复杂度的分析。

方法一：动态规划

        动态规划（DP）方法的核心思想是通过构建一个数组 dp[]，其中 dp[i] 表示构成数字 i 的最少完全平方数的个数。通过遍历所有小于等于当前数字 i 的完全平方数，更新 dp[i] 的值。

代码实现过程：

  1. 初始化：构造一个大小为 n+1 的 dp 数组，初始时所有 dp[i] 都设置为 INT_MAX，表示还未计算出最小完全平方数个数。
  2. 更新 dp[i]：对于每一个数字 i，遍历所有小于等于 i 的完全平方数 j * j，更新 dp[i] 的值，取 dp[i - j * j] + 1 的最小值。
  3. 返回结果：最终返回 dp[n]，即 n 所需的最少完全平方数个数。

时间复杂度：

  • 外层循环遍历 1 到 n，内层循环遍历每个 i 小于等于 sqrt(i) 的平方数，因此时间复杂度为 O(n * sqrt(n))。

空间复杂度：

  • 由于使用了一个大小为 n+1 的 dp 数组，因此空间复杂度为 O(n)。

方法二：数学方法（四平方和定理）

        根据 四平方和定理，每个正整数都可以表示为至多四个完全平方数之和。通过该定理可以更高效地求解该问题。

代码实现过程：

  1. 完全平方数检查：首先检查 n 是否是一个完全平方数。如果是，返回 1。
  2. Lagrange 四平方和定理应用：检查 n 是否符合 4^k * (8m + 7) 的形式。如果是，返回 4。这个条件是通过数学定理判断的，能直接得出结果。
  3. 两个完全平方数之和：如果前两步都没有得出结果，则遍历所有可能的平方数 i * i，检查 n - i * i 是否是一个完全平方数。如果是，返回 2。
  4. 返回 3：如果上述条件都没有满足，则根据四平方和定理返回 3。

时间复杂度：

  • 由于需要检查数字的平方根和除法操作，因此时间复杂度主要来源于判断是否符合 4^k * (8m + 7) 的形式（O(log n)）和遍历平方数（O(√n)）。因此，总的时间复杂度为 O(√n)。

空间复杂度：

  • 由于只使用了常数级别的额外空间，空间复杂度为 O(1)。

总结

  • 动态规划方法适用于广泛的问题类型，尤其是需要优化子问题求解过程的情况。通过逐步计算和存储最优解，可以在多次计算中避免重复计算。其缺点是空间复杂度相对较高。

  • **数学方法（四平方和定理）**则通过数学定理直接给出结果，能够在常数空间内高效求解。该方法的时间复杂度通常比动态规划方法要低，适用于对性能要求较高的场景。


http://www.kler.cn/a/394539.html

相关文章：

  • Iotop使用
  • Spring Cloud Gateway（分发请求）
  • Oracle 单机及 RAC 环境 db_files 参数修改
  • AUTOSAR_EXP_ARAComAPI的7章笔记（3）
  • QQ 小程序已发布，但无法被搜索的解决方案
  • python 同时控制多部手机
  • 【Excel】ToRow超级查找函数
  • 随机数
  • Spring Boot中的自动装配机制
  • 【竞技宝】CS2-上海majorRMR:美洲区最后门票争夺战
  • Spark 共享变量：广播变量与累加器解析
  • spring-webmvc根据请求路径找到对应的 HandlerMethod
  • [代码随想录Day11打卡] 150. 逆波兰表达式求值 239. 滑动窗口最大值 （有点难度） 347.前 K 个高频元素 （有点难度） 总结
  • 28、dawn
  • .NET 中的虚拟内存
  • 浅谈C#之多线程流式适配器
  • kafka如何知道哪个消费者消费哪个分区？
  • 单片机设计智能翻译手势识别系统
  • 「QT」窗口类 之 QWidget 窗口基类
  • 进入未来城：第五周游戏指南
  • 机器学习day4-朴素贝叶斯分类和决策树
  • ssm121开放式教学评价管理系统+vue(论文+源码)_kaic
  • java -jar`命令详解：运行JAR文件、传递参数与性能调优
  • 版本更新|大量云机风控指纹升级、新增安卓10系统！DuoPLus云手机新版本上线
  • 【人工智能】深入理解LSTM：使用Python构建文本生成模型
  • k8s上部署redis高可用集群