Leetcode-279. 完全平方数

描述

给定正整数 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.

来源:力扣(LeetCode)
链接:279. Perfect Squares

解题思路

这道题和之前的322. 零钱兑换这道题神似,可以将完全平方数当作各种可能用来组合的零钱,利用动态规划进行求解应该也是常规方法。不过本题的考察点除此之外,也是另有玄机的。比如四平方和定理

数学思路

说实话,第一次听说这个定理,这个定理主要是说每个正整数均可表示为4个整数的平方和,其实是可以表示为4个以内的平方数之和,那么就是说返回结果只有 1,2,3 或4其中的一个。

首先我们将数字简化一下,由于一个数如果含有因子4,那么我们可以把4都去掉,这样并不会影响结果,比如将8变成2,个数都是2,把12变成3,个数都是3,返回的结果都相同。另外一个可以化简的地方就是如果一个数除以8余7的话,那么肯定是由4个完全平方数组成,具体俺也不会证明。

接下来尝试将其拆分为两个平方数之和,如果拆成功了那么就会返回1或者2,因为其中一个平方数可能为0。

具体的代码实现请见解法一。

注意下面的 !!a + !!b 这个表达式,可能很多人不太理解这个的意思,其实很简单,感叹号!表示逻辑取反,那么一个正整数逻辑取反为0,再取反为1,所以用两个感叹号!!的作用就是看a和b是否为正整数,都为正整数的话返回2,只有一个是正整数的话返回1。

解法一是纯数学的角度,除此之外依然可以用动态规划的解法来做。

动态规划

找子问题

我们建立一个长度为n+1的一维数组dp,其中dp[i]代表到数字i组成最少完全平方个数,如果把dp数组都求解出来了,那么原问题也就迎刃而解了,其值即为dp[n]

确定状态

子问题只和一个变量–数字的位置相关。因此,序列中数的位置i就是状态,而状态i对应的值,就是组成正整数n所需要的最少完全平方数的个数。显然,状态一共有n+1个。

找出状态转移方程

假设dp[i]=x,则表示组成正整数i的最少完全平方数是x个,我们现在看看dp[i + j * j]会是如何,如果从正整数i + j * j的状态转移到正整数i的状态。 显然,因为要求最小值,dp[i + j * j]是其本身与dp[i] + 1两者之间较小的值,因为i + j * j比起i,起码会多一个完全平方数j

初始状态

dp数组按如下要求进行初始化:

  • dp[0] = 0
  • 其余初始化为INT_MAX

具体代码见解法二。

需要注意的是这里的写法,i必须从0开始,到n结束,是[0,n]的闭区间。j必须从1开始,因为我们的初衷是想用 dp[i] 来更新 dp[i + j * j],如果 i=0, j=0 了,那么 dp[i] 和 dp[i + j * j] 就相等了,怎么能用本身dp 值加1来更新自身。

BFS广度优先解法

下面再来看一个BFS的解法,第一次在题解当中抄BFS的解法,首先还是先让自己弄懂,但是在MOOC听了一遍以后就一直懵懵懂懂的状态。

可以看作从根节点0出发,往下搜索子节点,找到匹配则返回深度即可,相当于最短路径,即BFS广度优先搜索。

每层节点的子节点分别为父节点加上$(1, 4, 9, 16….(i^2 < n)$ 。使用队列存储节点,每次遍历前先获取当层节点数,即队列长度。然后依次遍历该节点子节点,如果长度符合则返回,不符合且是第一次访问,则添加到队列中去,如果已经访问过,则不需要添加。需要额外的哈希数组,用来存储访问过的元素,队列和哈希数组总共需要额外的2N的空间。搜索图如下:

搜索图

具体代码见解法三。

代码

解法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int numSquares(int n)
{
while (n % 4 == 0)
{
n /= 4;
}

if (n % 8 ==7)
return 4;

for (int a = 0; a * a <= n; a++)
{
int b = sqrt(n - a * a);
if(a * a + b * b == n)
{
return !!a + !!b;
}
}

return 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
int min(int a, int b)
{
if (a > b)
return b;
else
return a;
}

int numSquares(int n)
{
int dp[n+1];
dp[0] = 0;

for (int i = 1; i <= n; i++)
dp[i] = INT_MAX;

for (int i = 0; i <= n; i++)
{
for (int j = 1; i + j * j <= n; j++)
{
dp[i + j * j] = min(dp[i] + 1, dp[i + j * j]);
}
}

return dp[n];
}

解法三

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
/* BFS */

typedef struct {
int length, max;
int front, rear;
int *sq;
} queue;

queue* queueCreate(int k) {
queue* a;
if (k < 0)
return NULL;
else
a = (queue*) malloc(sizeof(queue));
if (!a)
return NULL;
else
{
a->max = k+1;
a->length = a->front = a->rear = 0;
a->sq = (int *)malloc(sizeof(int) * (k+1));
if (!a->sq)
{
free(a);
return NULL;
}
return a;
}
}

int enQueue(queue* obj, int value) {
if (obj->length == (obj->max - 1))
return 0;
else
{
obj->sq[obj->rear] = value;
obj->rear = (obj->rear + 1) % obj->max;
obj->length++;
}

return 1;
}

int deQueue(queue* obj) {
int head;

if (obj->front == obj->rear)
return 0;
else
{
head= obj->front;
obj->front = (obj->front + 1) % obj->max;
obj->length--;
return obj->sq[head];
}
}

int queueLength(queue *obj)
{
return obj->length;
}


int isEmpty(queue* obj) {
if (obj->front == obj->rear)
return 1;
else
return 0;
}

int isFull(queue* obj) {
if (obj->length == obj->max - 1)
return 1;
else
return 0;
}

void queueFree(queue* obj) {
free(obj->sq);
free(obj);
return;
}


int numSquares(int n){
int i,j,next, curr, size, steps = 0, *visited;
queue *q;

if (n == 0 || n == 1)
return n;

q = queueCreate(n + 1);
visited = (int *)malloc(sizeof(int) * (n+1));
for (i = 0; i <= n; i++)
visited[i] = 0;

//根节点入队列
enQueue(q, 0);
visited[0] = 1;

while(!isEmpty(q))
{
//深度加一
steps++;
size = queueLength(q);
for (i = 0; i < size; i++)
{
//遍历子节点
curr = deQueue(q);
for (j = 1; j * j <= n; j++)
{
next = curr + j*j;
if (next == n) return steps;
if (next > n) break;
if (visited[next]) continue;
//加入队列,以待访问其子节点
visited[next] = 1;
enQueue(q, next);
}
}
}
queueFree(q);
free(visited);
return steps;

}

参考