LeetCode – 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.

Example 1:

Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13 Output: 2 Explanation: 13 = 4 + 9.


 

解题1:

        数学方式的解法:基于四平方和理论(Lagrange's four-square theorem), 每个正整数均可表示为4个整数的平方和。 

         1. 如果整数包含因子4, 可以去掉不影响结果;

         2. 如果除8余7的话, 肯定是由四个完全平方数组成;

         3.  之后按照两个数的平方和拆解整数, 其中!!逻辑取反判断是否正整数还是0, 正整数!!后为1, 0!!后为0;    

         4. 其他情况结果返回3.

 

int numSquares(int n){
    while(n%4==0){
        n = n/4;
    }
    if (n%8 == 7 ){
        return 4;
    }
    for (int a=0;a*a<n;a++){
        int b = sqrt(n-a*a);
        if (a*a + b*b == n){
            return !!a+!!b;
        }
    }
    return 3;
}
int is_square(int n){
    int sqrt_n = sqrt(n);
    return (sqrt_n*sqrt_n == n);
}
int numSquares(int n){
    if (is_square(n)){
       return 1;
    }   
    while(n%4==0){
        n = n/4;
    }
    if (n%8 == 7 ){
        return 4;
    }
    for (int a=0;a*a<n;a++){
        if (is_square(n-a*a)){
           return 2;
        }
   }
    return 3;
}

时间复杂度O(N)

 


解题2:

        动态规划的解法:square[i] 表示正整数i能少能由多个完全平方数组成,对于每一个i, 必须是一个数字i-j*j和一个完全平方和j*j的和

 
class Solution 
{
public:
    int numSquares(int n) {
        if (n <= 0){
            return 0;
        }
        vector<int> square(n+1, INT_MAX);
        square[0] = 0;
        for (int i=1; i<=n; i++){
            for (int j=1; j*j<=i;j++){
                square[i] = min( square[i] ,  square[i-j*j] + 1 );
            }
        }
        return square[n];
    }
};

时间复杂度O(N*N)

解题3:

        广度优先BFS的解法:

  1. 设置perfectSquares包含所有平方和小于n的完全平方和,cntPerfectSquares[i-1]记录最少多少个完全平方和的sum可以达到i;
  2. 如果perfectSquares最后一个数等于n,返回1;
  3. 创建查询队列,将perfectSquares插入队列;
  4. 由于perfectSquares存放平方和信息,计数currCntPerfectSquares =1,
  5. currCntPerfectSquares +1, 弹出队列,与所有perfectSquares中的完全平方和组合, 如果刚好等于N返回currCntPerfectSquares;
  6. 如果当前弹出的完全平方和与对应的perfectSquares中的完全平方和小于n, 并且对应的cntPerfectSquares记录为-,更新记录为currCntPerfectSquares,并放入队列,下一个循环继续处理
  7. 如果当前弹出的完全平方和与对应的perfectSquares中的完全平方和大于n,跳出,进行下一次队列弹出,再与perfectSquares匹配。

  class Solution {
public:
    int numSquares(int n) {
        if (n<=0){
            return 0;
        }
        
        vector<int> perfectSquares;
        vector<int> cntPerfectSquares(n+1, 0);
        queue<int> searchQ;
        for (int i = 1; i*i <= n; i++)
        {
            int m= i*i;
            perfectSquares.push_back(m);
            cntPerfectSquares[m-1] = 1;
            searchQ.push(m);
            
        }
        
        if (perfectSquares.back() == n)
        {
            return 1;
        }
        
        int currCntPerfectSquares = 1;
        while (!searchQ.empty())
        {
            currCntPerfectSquares++;
            int searchQSize = searchQ.size();
            
            for (int i=0; i<searchQSize; i++){
               
                int tmp = searchQ.front();
                
                for (auto& j: perfectSquares){
                    if (tmp +j == n){
                        return currCntPerfectSquares;
                    }
                    else if ((tmp+j<n) && cntPerfectSquares[tmp+j-1] == 0){
                        cntPerfectSquares[tmp+j-1] = currCntPerfectSquares;
                        searchQ.push(tmp+j);
                    }
                    else if(tmp +j >n){
                        break;
                    }
                }
                searchQ.pop();
            }
        }
        return 0;
    }
};
时间复杂度O(N*N)

 

参考

[LeetCode] 279. Perfect Squares 完全平方数

[Leetcode] #279 Perfect Squares (BFS, DP)

Summary of 4 different solutions (BFS, DP, static DP and mathematics)

 

 

Be First to Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注