279. Perfect Squares

ゝ一纸荒年。 2021-10-01 02:22 206阅读 0赞

本周依旧是做与图论相关的题目，作为对图论知识的巩固。

**题目：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.

**题解**  
题目的要求是，给定一个数，给出这个数最少能够用多少个perfect number求出来。perfect number的定义是正整数的平方(1,4,9,16,...)这道题很容易让人联想到的是动态规划或者是搜索（深度优先搜索、广度优先搜索），这次我尝试通过基于搜索来解决。与BFS相比，DFS求出来的解，并不一定是个数最少的解，因此，在这道题，我选择了BFS来解决。具体的做法如下：

*  与一般情况相同，BFS都是通过队列实现的，每次迭代的时候出队一个元素，然后与它相关的元素放到队列的末尾
 *  定义一个结构体N，代表当前的数值(n)以及当前经历了多少次加法(level)，N作为队列中元素的类型
 *  每从队列中取出一个元素，将它分别与小于该元素的n的perfect number作差值，假设得到的差值为diff,将(diff,level+1)加入到队列中
 *  直到队列中没有元素，结束循环

这个解题方法的算法复杂度为O(sqrt(n)\*sqrt(n)) = O(n)

**代码**

class Solution {
    public:
        struct N
        {
            int level; // level
            int n;   // num
            N(int _n,int _level)
            {
                n   = _n;
                level = _level;
            }
        };
        
        int numSquares(int n) {
            int res = 0;
            queue<N> q;
            q.push(N(n,0));  //先将最初的数入队
            
            while(!q.empty())
            {
                N currnum = q.front();
                q.pop();
                for (int i = int(sqrt(currnum.n)) ; i > 0 ; i--)
                {
                    int newn = currnum.n - i * i; // 队头的数字减去一个perfect number，再入队
                    if(newn == 0) 
                        return currnum.level+1; // 得到答案
                    else
                        q.push(N(newn,currnum.level+1));
                }
            }
            
            return res;
        }
    };

转载于:https://www.cnblogs.com/MT-ComputerVision/p/6624453.html