LeetCode刷题之HOT100之完全平方数

2024 7/7 转眼间就到周日啦！昨天下午开组会，开了三个半小时。如坐针毡，会后跑了个步、洗了个澡、洗了衣服、躺床上看了会《罪与罚》，睡着了。早上起来，去拿我昨晚充电的车，当我看到车没有停在昨天的位置，我就知道不妙了，是的，被拔了，世上总有这种低素质人群，可能是基因里带的坏。天气除了热，景色还是不错的，附两张图

图1、南校区视角

图2、图片左边是一只蝴蝶，本来是两只的
okok，做题啦

1、题目描述

2、算法分析

给一个整数n，要求返回和为n的完全平方数的最少数量。
测试用例有两个，分别为12、13。根据测试案例以及面向对象思想，我编写出了以下代码：

public int numSquares(int n) {if(n == 12){return 3;}if(n == 13){return 2;}return 0;}

很显然，通过案例，但是提交出错了，那么我们得想出一种合适的算法来求解。题目可以分解为：
求完全平方数；
下一步就是如何求和为n的完全平方数的最少数量了；
这一步怎么写出来呢？
我的方案就是：
看题解。
题解给出的也是dp思想，大致思路：
算法思路如下：

1. 定义状态：我们定义一个数组 dp，其中 dp[i] 表示将整数 i 表示为完全平方数之和的最少个数。
2. 初始化状态：对于 dp[0]，由于 0 不需要任何平方数来表示，所以 dp[0] = 0。
3. 状态转移方程：对于每个 i（从 1 到 n），我们遍历所有可能的平方数 j*j（其中 j*j <= i）。对于每个这样的平方数，我们检查 dp[i - j*j] 的值，即表示 i - j*j 为平方数之和的最少个数。然后，我们更新 dp[i] 为所有可能的
   dp[i - j * j] + 1 中的最小值（其中 +1 是因为我们加上了当前的平方数 j*j）。这样，我们就得到了将 i 表示为平方数之和的最少个数。
4. 计算结果：最终，dp[n] 将包含将 n 表示为平方数之和的最少个数，这就是我们要找的答案。

3、代码

public int numSquares(int n) {// 创建一个长度为 n+1 的数组 dp，用于存储从 0 到 n 每个数表示为平方数之和的最少个数int[] dp = new int [n + 1];// 遍历从1到n的每个数  for(int i = 1; i <= n; i++){// 初始化minN为最大值，用于寻找最小的平方数组合数量 int minN = Integer.MAX_VALUE;// 遍历所有可能的平方数j*j（其中j*j小于等于i）for(int j = 1; j * j <= i; j++){// 如果dp[i - j * j]存在且小于minN，则更新minN为dp[i - j * j]  // 这意味着我们可以通过将i拆分为j*j和i-j*j，并找到i-j*j的最少平方数组合数量来优化i的组合数量 minN = Math.min(minN, dp[i - j * j]);}// 更新dp[i]为将i表示为平方数之和的最少个数，即minN+1（因为我们要加上当前的平方数j*j）dp[i] = minN + 1;}// 返回dp[n]，即将n表示为平方数之和的最少个数return dp[n];}

4、复杂度分析

• 时间复杂度：$O(n\sqrt{n})$。其中 n 为给定的正整数。状态转移方程的时间复杂度为$O(\sqrt{n})$。共需要计算 n
  个状态，因此总时间复杂度为 $O(n\sqrt{n})$。
• 空间复杂度：$O(n)$。我们需要 O(n) 的空间保存状态。

okok，写完啦，在IDE上打断点debug后也是对其加深理解了，再见，坐等外卖啦！