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

糖逗

题目描述：

1. 给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
   
2. 
   
3. 示例 1:
   
4. 
   
5. 输入: n = 12
   
6. 输出: 3
   
7. 解释: 12 = 4 + 4 + 4.
   
8. 示例 2:
   
9. 
   
10. 输入: n = 13
    
11. 输出: 2
    
12. 解释: 13 = 4 + 9.
    
13. 
    
14. 来源：力扣（LeetCode）
    
15. 链接：https://leetcode-cn.com/problems/perfect-squares
    
16. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. #include <queue>
   
2. #include <iostream>
   
3. #include <algorithm>
   
4. 
   
5. using namespace std;
   
6. 
   
7. int solution(int n){
   
8.         int celling = pow(n, 0.5);
   
9.         queue<int> temp;
   
10.         temp.push(0);
    
11.         int step = 0;
    
12.         int sum = 0;
    
13.         while(!temp.empty()){
    
14.                 step++;
    
15.                 int len = temp.size();
    
16.                 for(int i = 0; i < len;i++){
    
17.                         int front = temp.front();
    
18.                         temp.pop();
    
19.                         for(int j = 1; j <= celling; j++){
    
20.                                 int sum = front + pow(j, 2);
    
21.                                 if(sum==n) return step;
    
22.                                 if(sum > n) continue;
    
23.                                 temp.push(sum);
    
24.                         }
    
25.                 }
    
26.         }
    
27.         return -1;
    
28. }
    
29. 
    
30. 
    
31. 
    
32. int main(void){
    
33.         int input;
    
34.         cin >> input;
    
35.         cout << solution(input) << endl;
    
36.         return 0;
    
37. }

复制代码

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