LeetCode 279. 完全平方和
原题链接
中等
class Solution {
public:
int numSquares(int n) {
queue<int> q;//定义一个队列,用来存储每一步得到的全部结果;
int dist[n+1];//定义一个数组用来存储带某个点时的步数;
for(int i=1;i<=n;i++){//遍历数组,将除了0的其他位置变为无穷大
dist[i]=INT_MAX;
}
q.push(0);//将队列放入一个数
dist[0]=0;//使从0开始到0是0步;
while(q.size()){//循环到size==0;
int t=q.front();//取出队列里的第一个数(注意队列是先进先出),存在t里
q.pop();//将这个数弹出
if(t==n)//如果t与n相等,那么结束循环,因为是BFS所以最短就是最先。
return dist[t];
for(int i=1;i*i+t<=n;i++){//从1到i*i+t<=n循环
int j=i*i+t;
if(dist[j]>dist[t]+1){//这是代替条件,只有带这个点的之前记录下的步数比现在到达这个点的步数大,才可以替换
dist[j]=dist[t]+1;
q.push(j);//将这个点存进这一步
}
}
}return 0;
}
};