C++刷leetcpde（279. 完全平方数）【广度优先搜索】

糖逗

题目描述：

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

示例 1:

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

输入: n = 13
输出: 2
解释: 13 = 4 + 9.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/perfect-squares
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include <queue>
#include <iostream>
#include <algorithm>

using namespace std;

int solution(int n){
        int celling = pow(n, 0.5);
        queue<int> temp;
        temp.push(0);
        int step = 0;
        int sum = 0;
        while(!temp.empty()){
                step++;
                int len = temp.size();
                for(int i = 0; i < len;i++){
                        int front = temp.front();
                        temp.pop();
                        for(int j = 1; j <= celling; j++){
                                int sum = front + pow(j, 2);
                                if(sum==n) return step;
                                if(sum > n) continue;
                                temp.push(sum);
                        }
                }
        }
        return -1;
}



int main(void){
        int input;
        cin >> input;
        cout << solution(input) << endl; 
        return 0;
} 

注意事项：
1.题目要求是最小步数，如果使用普通的深度优先搜索并不一定返回步数最小的答案，只能返回找到的第一个答案的步数。
2.这里广度优先搜索的queue能够保证每次step时候，queue中的队首是大的元素，队尾是小的元素。