leetcode--279 完全平方数

 

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例 1:

输入: n = 12
输出: 3 
解释: 12 = 4 + 4 + 4.

示例 2:

输入: n = 13

输出: 2
解释: 13 = 4 + 9

解题思路：当没有仔细看题目时先想到了贪心算法，即13=1+1+1+1+9，但题目中要求最小平方数，所以考虑其他方法

BFS建模：考虑将问题转为图论问题处理，从n到0共n+1个节点，每个节点是一个数，如果两个节点Vi Vj相差一个完全

平方数，则连接Vi Vj为一条边，这样就得到了一个无权图，原问题转为求n到0的最短路径。利用下图说明的原理：

例如当输入n=5时，

1 在[0, n]范围内找到与n相差一个完全平方数的4和1，并记录节点出现的次数，即将（4,1）(1, 1)存入队列中，

2 从队列中弹出4，从4出发寻找与4相差一个完全平方数的3和0，并将(3, 2)(0, 2)存入队列；

3 从队列中弹出1，从1出发寻找与1相差一个完全平方数的0，并将(0, 2)存入队列

4 从队列中弹出3，从3出发寻找与3相差一个完全平方数的2，并将(2, 3)存入队列

5 从队列中弹出0，发现已经到0了，对应的路径为最短路径，即0节点对应的次数2

具体代码：

class Solution {
public:
    int numSquares(int n) {
        queue<pair<int, int>> q;
        q.push(make_pair(n, 0));
        while (q.size() != 0)
        {
            //q.push();
            pair<int, int> temp = q.front();
            q.pop();
            n = temp.first;
            int step = temp.second;

            if (n==0)
            {
                return step;
            }

            for (int i = 1; n-i*i>=0; i++)
            {
                q.push(make_pair(n-i*i, step+1)); // 从n到n-i*i走了step步
            }

        }

        return 0;
    }
};

改进：由于不同的路径会到达同一个节点，导致队列中记录了同一个节点的重复信息，导致上述的超时，而实际上求最短路径时每个节点只能出现一次，也就是说当发现一个节点已经出现在队列中时，就不再存储其相关信息，这样能够大幅降低时间消耗

class Solution {
public:
  int numSquares(int n)
    {
        queue<pair<int, int>> q;
        q.push(make_pair(n, 0));
        vector<bool> hasVisited(n+1, false);   //初始化为0
        hasVisited[n] = true;     //
      
        while (q.size() != 0)
        {
            n = q.front().first;
            int step = q.front().second;
            q.pop();

            if (n==0)
            {
                return step;
            }

            for (int i = 1; ; i++)
            {
                int tmp = n - i*i;

                if (tmp<0)
                {
                    break;
                }

                if (!hasVisited[tmp])            //访问过的节点不再访问
                {
                    q.push(make_pair(tmp, step + 1)); // 从n到n-i*i走了step步
                    hasVisited[tmp] = true;    //访问过的节点置为true
                }
            }

        }

        return 0;
    }

};