完全平方数

完全平方数

题目描述

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

示例1

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

示例2

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

分析

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

参考代码

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
30
31
32
33
34
35
36
37
38
39
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;
}
};
作者

瑾年

发布于

2021-07-17

更新于

2021-07-17

许可协议

CC BY-NC-SA 4.0

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×