Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.
int numSquares(int n) {
if(n <= 2){
return n;
}
int min = n, temp = 0;
for( int i = 2; i * i <= n; i++){
if(n % (i * i) == 0){
temp = n / (i * i);
}else{
temp = n / (i * i) + numSquares(n % (i * i));
}
if(temp < min){
min = temp;
}
}
return min;
}
有点类似 perfect squares那道题-279.
LeetCode 279. Perfect Squares Description Given a positiv...
279. Perfect Squares（Medium) Given a positive integer n, ...
原题：279. Perfect Squares Given a positive integer n, find ...
279. Perfect Squares image.png参考： https://www.geeksforgee...
0X00 leetcode 做了 4 道 leetcode 279. Perfect Squares leetco...
278. First Bad Version 二分查找的思路 279. Perfect Squares 使用动态规...
https://leetcode.com/problems/perfect-squares/description...
第一种做法是动态规划，用一个数组perfect[i]来记录到perfect[i]数目，perfect[0]=0，对...
问题 Given a positive integer n, find the least number of p...
本文标题：279. Perfect Squares
本文链接：https://www.haomeiwen.com/subject/rddrrttx.html
网友评论