题目
给你一个整数
n
,返回 和为n
的完全平方数的最少数量 。
输入: n = 12 输出: 3 解释: 12 = 4 + 4 + 4
思路一
我们先创建一个array变量,他是一个做为储存状态的数组,他的长度是形参n+1,默认值全为0,我们用该数组来记录当前数值的所需完全平方数的最少数量,然后再使用循环对形参n进行循环,在循环中我们创建一个min变量他的值是Number的最大值,然后再使用循环对第一层循环的i变量进行循环,我们在该循环中使用Math.min函数获取当前min变量和array数组的
i-j*j
的最小值,然后我们将其得出的最小值重新赋值给min变量,依次往复,求出当前所需完全平方数的最少数量,然后将min变量+1赋值给array的i变量位置,最后我们将array的形参n位置的数据返回出去即可
var numSquares = function(n) { let array = new Array(n+1).fill(0); for(let i=1; i<=n; i++){ let min = Number.MAX_VALUE; for(let j=1; j*j<=i; j++){ min = Math.min(min, array[i - j * j]); } array[i] = min + 1; } return array[n]; };
思路二
我们在先声明一个s变量,它的值是形参n与0.5进行乘方在使用Math.floor方法向下取整后的值,然后我们在判断当前s变量和s变量想乘是否等于n,如果等于则返回1,如果不是我们接下来声明f变量他的值默认是n,然后再判断f和8相余是否等于7,如果是则直接返回4,如果不是则进行循环,判断当前f变量和4相余是否等于0,如果是则一直进行循环,在循环中我们将f变量和4相除最后把值在赋值给f变量,在判断f变量和8相余是否等于7,如果是则直接返回4,则下来在声明一个a变量,默认值为0,然后再进行循环,当前的变量a和变量a相乘是否小于形参n,如果是则进入循环,在循环中我们使用Math.floor方法向下取整通过
( n - a*a ) ** 0.5
该公式得出的值,然后进行判断b*b + a*a === n
,如果满足则直接返回2,如果不是则将变量a自增1,循环结束后,如果没有返回值则直接返回3
var numSquares = function(n) { let s = Math.floor(n ** 0.5); if( s*s === n ) return 1; let f = n if(f % 8 === 7) return 4; while( f % 4 === 0 ){ f /= 4 if(f % 8 === 7) return 4; } let a = 0 while( a*a < n ){ b = Math.floor(( n - a*a ) ** 0.5) if( b*b + a*a === n ) return 2 a++ } return 3 };