• Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

    For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

    Credits:
    Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

题意

给定一个正整数，找到最少的平方数可以组成的个数。

比如12 可以由12个1组成（1是平方数），也可以由3个4组成，也可以由一个9，三个1组成，最少的是3个4.所以返回3.

答案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int numSquares(int n)
{
    assert(n>0);
    queue<pair<int,int> > q;
    q.push(make_pair( n, 0));
    vector <bool> visited(n+1,false);
    visited[n] = true;
    
    while(!q.empty())
    {
        int num =q.front().first;
        int step =q.front().second;
        q.pop();
        
        if(num==0) return step;
        
        for(int i=1; num-i*i>=0; i++)
        {
            if(!visited[num-i*i] )
            {
                q.push(make_pair(num-i*i, step+1));
                visited[num-i*i] = true;
            }
        }
    }
}
};

思路

给出一个正整数n,寻找最少的完全平方数，使他们的和为n。

对问题建模，把整个问题转化为一个图论问题，从n到0，每个数字表示一个节点，如果两个数字x到y相差一个完全平方数，则连接一条边，就得到了一个无权图，原问题就转换为求这个无权图中从n到0的最短路径。

加入n为12，首先把12入队，然后把最大的11入队，然后把8入队，然后把3入队，他们入队的同时，step都为1。然后取11，再把10入队，7入队，2入队，他们的step都为2，然后对于8，把7入队，4入队。step=2,对于3，把2入队。step=2.因为他们的速度都是相同的，所以只要有一个数num==0,此时的step就是最小的step，所以直接返回即可。

同时，为了防止重复入队，设置一个vector,重复的就不用再入队了。