LeetCode 1634. 求兩個多項式鏈錶的和

Michael阿明 2021-08-15 22:28:28 阅读数:659

本文一共[544]字,预计阅读时长:1分钟~
leetcode

文章目錄

1. 題目

多項式鏈錶是一種特殊形式的鏈錶,每個節點錶示多項式的一項。

每個節點有三個屬性:

  • coefficient:該項的系數。項 9x4 的系數是 9 。
  • power:該項的指數。項 9x4 的指數是 4 。
  • next:指向下一個節點的指針(引用),如果當前節點為鏈錶的最後一個節點則為 null 。

例如,多項式 5x3 + 4x - 7 可以錶示成如下圖所示的多項式鏈錶:

在這裏插入圖片描述

多項式鏈錶必須是標准形式的,即多項式必須 嚴格 按指數 power 的遞减順序排列(即降幂排列)。
另外,系數 coefficient 為 0 的項需要省略

給定兩個多項式鏈錶的頭節點 poly1 和 poly2,返回它們的和的頭節點。

PolyNode 格式:

輸入/輸出格式錶示為 n 個節點的列錶,其中每個節點錶示為 [coefficient, power] 。例如,多項式 5x3 + 4x - 7 錶示為: [[5,3],[4,1],[-7,0]] 。

示例 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 = 2x^2 + 4x + 3. poly2 = 3x^2 - 4x - 1. 和為 5x^2 + 2. 注意,我們省略 "0x" 項。
示例 3:
輸入:poly1 = [[1,2]], poly2 = [[-1,2]]
輸出:[]
解釋:和為 0。我們返回空鏈錶。
提示:
0 <= n <= 10^4
-10^9 <= PolyNode.coefficient <= 10^9
PolyNode.coefficient != 0
0 <= PolyNode.power <= 10^9
PolyNode.power > PolyNode.next.power

來源:力扣(LeetCode)
鏈接:https://leetcode-cn.com/problems/add-two-polynomials-represented-as-linked-lists
著作權歸領扣網絡所有。商業轉載請聯系官方授權,非商業轉載請注明出處。

2. 解題

/** * Definition for polynomial singly-linked list. * 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) {}; * }; */
class Solution {

public:
PolyNode* addPoly(PolyNode* poly1, PolyNode* poly2) {

PolyNode* temp = new PolyNode(), *cur=temp;
while(poly1 && poly2)
{

if(poly1->power > poly2->power)
{

cur->next = poly1;
cur = cur->next;
poly1 = poly1->next;
}
else if(poly1->power < poly2->power)
{

cur->next = poly2;
cur = cur->next;
poly2 = poly2->next;
}
else
{

int sum = poly1->coefficient + poly2->coefficient;
if(sum)
{

poly1->coefficient += poly2->coefficient;
cur->next = poly1;
cur = cur->next;
}
poly1 = poly1->next;
poly2 = poly2->next;
}
}
if(poly1)
cur->next = poly1;
else
cur->next = poly2;
return temp->next;
}
};

88 ms 37.8 MB C++


我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號(Michael阿明),一起加油、一起學習進步!
Michael阿明

版权声明:本文为[Michael阿明]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/08/20210815222753159v.html