LeetCode热题100 完全平方数

题目描述给你一个整数 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 1 n 10^41n104思路1: 动态规划我们考虑f[i]为第i个数需要的最少完全平方数的个数枚举每个比他小的完全平方数j 2 j ^ 2j2,则有f [ i ] f [ i − j 2 ] 1 f[i] f[i - j ^ 2] 1f[i]f[i−j2]1 这里的1就是j 2 j ^ 2j2, 我们枚举每个j的时间复杂度是 o(n \sqrt{n}n​), 枚举i的时间复杂度为o(n)总的时间复杂度为o ( n n ) o(n\sqrt{n})o(nn​)。代码1classSolution{public:intnumSquares(intn){vectorintf(n1,0);unordered_setints;// 记录这个数是不是完全平方数for(inti1;i100;i){s.insert(i*i);}for(inti1;in;i){f[i]INT_MAX;// 需要j^2一个, 剩下的i - j ^ 2的最少个数已经出现for(intj1;ji/j;j){f[i]min(f[i],1f[i-j*j]);}}returnf[n];}};思路2: 数学四平方和定理有两个结论任意一个正整数都可以被表示为至多四个正整数的平方和。当且仅当n ≠ 4 k × ( 8 m 7 ) n \neq 4^k \times (8m 7)n4k×(8m7)时n nn可以被表示为至多三个正整数的平方和。因此当n 4 k × ( 8 m 7 ) n 4^k \times (8m 7)n4k×(8m7)时n nn只能被表示为四个正整数的平方和。此时我们可以直接返回 4。我们枚举答案的个数当 可以开方,o(1),答案为1当 可以表示成两个数完全平方和相加o ( n ) o(\sqrt{n})o(n​)答案为2当 可以表示成n 4 k × ( 8 m 7 ) n 4^k \times (8m 7)n4k×(8m7)o(logn), 答案为4否则答案为3因此总的时间复杂度为o ( n ) o(\sqrt{n})o(n​)。代码2classSolution{public:// 是否是完全平方数 o(1)boolisPerfectSquare(intx){intysqrt(x);returny*yx;}// 是否是两个数完全平方相加 o(n ^ (1/2))boolisTwoPerfectSquareadd(intx){for(inti1;ix/i;i){intjx-i*i;if(isPerfectSquare(j)){returntrue;}}returnfalse;}// 是否是4个数相加 o(logn)boolcheckAnswer4(intx){while(x%40){x/4;}returnx%87;}intnumSquares(intn){if(isPerfectSquare(n))return1;if(checkAnswer4(n))return4;if(isTwoPerfectSquareadd(n))return2;return3;}};