LeetCode[279. 完全平方数]

279. 完全平方数

• 本题我们可以把他理解成一个图论
• 我们的每一个结点就是每一个数值
• 加了平方项以后就从当前值转移到了另一个值
• BFS常见套路
  • 定义一个队列，队列中有元素就一直循环
  • 初始时刻我们把起始点放入队列中，同时距离设置为0
  • 每次循环取出队头，弹出队头
  • 对我们取出来的队头做一定的处理
  • 得到新的结果，存到队列中

class Solution {
public:
    int numSquares(int n) {
        queue<int> q;
        vector<int> dist(n + 1,INT_MAX);//定义距离，所有点到起点的距离
        q.push(0);
        dist[0] = 0;//起点是0
        while(q.size()){
            int t = q.front();//当前点
            q.pop();
            if(t == n) return dist[t];//走到了终点
            //否则我们枚举当前点t可以走到哪些点
            for(int i = 1; i * i + t <= n; i++){
                int j = t + i * i;
                if(dist[j] > dist[t] + 1){//说明我们的j可以从t过来
                    dist[j] = dist[t] + 1;//更新我们的j值
                    q.push(j);
                }
            }       
        }
        return 0;
    }
};