算法数据结构

链表维护多项式的加法

字数统计: 831字   |   阅读时长: 3分
,

摘要: 链表维护多项式加法，力扣 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