题目描述

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

示例1

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

示例2

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

分析

  1. 采用队列BFS,第一次(相当于第一层),依次对分别对root减去1,4,9… (减数要小于root)
  2. 判断减完后的结果是否为0,如果不是,加入队列中。如果是,则返回层数。
  3. 取出队列中的元素,进行再一轮(层)减法,然后判断。重复步骤二,直到结束。
  4. 画图类似与一个多叉树。

参考代码


class Solution {
public:
int numSquares(int n) {
queue <int> q ;
vector<bool> exit(n,false) ;
int temp = n ;
for(int i = 0 ,j = 1 ; j*j <= temp ;++i ,++j)
{
if(temp - j*j == 0)
{
return 1 ;
}
q.push(temp-j*j);
exit[temp-j*j] = true ;
}

int step = 1 ;
while(!q.empty())
{
int len = q.size();
for(int i = 0 ; i < len ; ++i)
{
int num = q.front();
q.pop();
for(int i = 0 , j = 1 ; j*j <= num ; ++i,++j)
{
if(num - j*j == 0)
{
return ++step;
}
// 避免队列里有重复数字
if(exit[num-j*j] == false) {q.push(num-j*j);}
}
}
++step;
}
return step;
}
};

谢谢访问