你的位置:首页 > Java教程

[Java教程]279. Perfect Squares


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.

代码如下:

 1 public class Solution { 2   public int numSquares(int n) { 3     if(n<=2) 4     return n; 5      6     int min=n,t=0; 7     for(int i=2;i*i<=n;i++) 8     { 9       int c=i*i;10       if(n%c==0)11       t=n/c;12       else13         t=n/c+numSquares(n%c);14         if(t<min)15         min=t;16     }17     return min;18   }19 }