链表维护多项式的加法

  |  

摘要: 链表维护多项式加法,力扣 1634

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


链表的一种应用是维护多项式,本文我们通过一个题目看一下如何用链表进行多项式的存储,以及两个多项式链表如何求和。


题目

多项式链表是一种特殊形式的链表,每个节点表示多项式的一项。

每个节点有三个属性:

  • coefficient:该项的系数。项 $9x^{4}$ 的系数是 9 。
  • power:该项的指数。项 $9x^{4}$ 的指数是 4 。
  • next:指向下一个节点的指针(引用),如果当前节点为链表的最后一个节点则为 null 。

例如,多项式 $5x^{3} + 4x - 7$ 可以表示成如下图所示的多项式链表:

多项式链表必须是标准形式的,即多项式必须 严格 按指数 power 的递减顺序排列(即降幂排列)。另外,系数 coefficient 为 0 的项需要省略。

给定两个多项式链表的头节点 poly1 和 poly2,返回它们的和的头节点。

PolyNode 格式:

输入/输出格式表示为 n 个节点的列表,其中每个节点表示为 [coefficient, power] 。例如,多项式 $5x^{3} + 4x - 7$ 表示为: [[5,3],[4,1],[-7,0]] 。

提示:

1
2
3
4
5
0 <= n <= 1e4
-1e9 <= PolyNode.coefficient <= 1e9
PolyNode.coefficient != 0
0 <= PolyNode.power <= 1e9
PolyNode.power > PolyNode.next.power

示例 1:

输入:poly1 = [[1,1]], poly2 = [[1,0]]
输出:[[1,1],[1,0]]
解释:poly1 = x. poly2 = 1. 和为 x + 1.

示例 2:
输入:poly1 = [[2,2],[4,1],[3,0]], poly2 = [[3,2],[-4,1],[-1,0]]
输出:[[5,2],[2,0]]
解释:poly1 = 2x2 + 4x + 3. poly2 = 3x2 - 4x - 1. 和为 5x2 + 2. 注意,我们省略 “0x” 项。

示例 3:
输入:poly1 = [[1,2]], poly2 = [[-1,2]]
输出:[]
解释:和为 0。我们返回空链表。


题解

算法:链表

一个节点代表多项式的一项,节点中持有的属性如下:

1
2
3
4
5
6
7
struct PolyNode {
int coefficient, power;
PolyNode *next;
PolyNode(): coefficient(0), power(0), next(nullptr) {};
PolyNode(int x, int y): coefficient(x), power(y), next(nullptr) {};
PolyNode(int x, int y, PolyNode* next): coefficient(x), power(y), next(next) {};
};

一个表示多项式的链表,节点按 power 降序排列。系数为 0 的节点省略。

代码 (C++)

给两个多项式链表,求和后返回结果的多项式链表。

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
class Solution {
public:
PolyNode* addPoly(PolyNode* poly1, PolyNode* poly2) {
if(!poly2) return poly1;
if(!poly1) return poly2;
PolyNode *dummy = new PolyNode(0, 0);
PolyNode *iter = dummy;
PolyNode *it1 = poly1, *it2 = poly2;
while(it1 && it2)
{
if(it1 -> power == it2 -> power)
{
int p = it1 -> power;
int c = it1 -> coefficient + it2 -> coefficient;
if(c != 0)
iter -> next = new PolyNode(c, p);
it1 = it1 -> next;
it2 = it2 -> next;
}
else if(it1 -> power > it2 -> power)
{
iter -> next = new PolyNode(it1 -> coefficient, it1 -> power);
it1 = it1 -> next;
}
else
{
iter -> next = new PolyNode(it2 -> coefficient, it2 -> power);
it2 = it2 -> next;
}
if(iter -> next)
iter = iter -> next;
}
while(it1)
{
iter -> next = new PolyNode(it1 -> coefficient, it1 -> power);
it1 = it1 -> next;
iter = iter -> next;
}
while(it2)
{
iter -> next = new PolyNode(it2 -> coefficient, it2 -> power);
it2 = it2 -> next;
iter = iter -> next;
}
return dummy -> next;
}
};

Share