279.完全平方数

题目描述

题解一(动态规划)

思路

代码

classSolution{publicintnumSquares(intn){// dp[i] 表示和为 i 的完全平方数的最少数量int[]dp=newint[n+1];// 初始化为最大值，方便后续求最小值Arrays.fill(dp,Integer.MAX_VALUE);//-----------------------//解析1:Arrays.fill()方法///----------------------// base case：和为 0 的完全平方数数量为 0dp[0]=0;// 遍历所有需要求的数字 ifor(inti=1;i<=n;i++){// 尝试减去所有可能的完全平方数 j*j (1, 4, 9, 16...)for(intj=1;j*j<=i;j++){// 状态转移方程dp[i]=Math.min(dp[i],dp[i-j*j]+1);}}returndp[n];}}

解析1:Arrays.fill()方法

将一个数组中的所有元素（或指定范围的元素），快速统一替换为你指定的某一个值

//1.把 arr 里的所有元素都变成 9Arrays.fill(arr,9);//2.从索引 1 开始（包含），到索引 4 结束（不包含索引 4）//即把arr数组中[1,4)索引对应的元素替换为7Arrays.fill(arr,1,4,7);

复杂度分析

• 时间复杂度：O(nn)O(n \sqrt{n})O(nn​)。外层循环执行nnn次，内层循环对于每个iii，最多执行i\sqrt{i}i​次，因此总复杂度为O(nn)O(n \sqrt{n})O(nn​)
• 空间复杂度：O(n)O(n)O(n)。我们需要一个长度为n+1n + 1n+1的 dp 数组来存储中间状态

题解二(数学)(最优解法)

代码

classSolution{publicintnumSquares(intn){// 判断是否为完全平方数的辅助方法if(isPerfectSquare(n)){return1;}// 判断是否满足 4^a * (8b + 7)// 这一步是消去式子中的 4^a，也就是不断将 n 除以 4inttemp=n;while(temp%4==0){temp/=4;}// 如果消去 4^a 后，除以 8 的余数是 7，则必定是由 4 个平方数组成if(temp%8==7){return4;}// 判断是否能由 2 个平方数组成 (n = a^2 + b^2)for(inti=1;i*i<=n;i++){intj=n-i*i;if(isPerfectSquare(j)){return2;}}// 如果不是 1, 4, 2，那就只能是 3 了return3;}// 辅助方法：判断一个数是否为完全平方数privatebooleanisPerfectSquare(intx){inty=(int)Math.sqrt(x);returny*y==x;}}

复杂度分析

• 时间复杂度：O(n)O(\sqrt{n})O(n​)
  • 判断答案是否为 1 耗时O(1)O(1)O(1)。
  • 判断答案是否为 4 涉及一个 while 循环（除以 4），最多执行log⁡4(n)\log_4(n)log4​(n)次，耗时O(log⁡n)O(\log n)O(logn)。
  • 判断答案是否为 2 涉及一个 for 循环，循环变量 i 最大到n\sqrt{n}n​，内部判断耗时O(1)O(1)O(1)，总共耗时O(n)O(\sqrt{n})O(n​)。
  • 综合起来，最高阶的时间复杂度为O(n)O(\sqrt{n})O(n​)。
• 空间复杂度：O(1)O(1)O(1)。只使用了几个整型变量，不需要额外的数组或集合来存储中间状态（相比于动态规划省下了O(n)O(n)O(n)的内存空间）