目录
链表相加（⼆）（链表+⾼精度加法）
题目解析
讲解算法原理
编写代码
⼤数乘法（⾼精度乘法）
题目解析
讲解算法原理
辨析代码
链表相加（⼆）（链表+⾼精度加法）
题目解析
1.题目链接：链表相加(二)_牛客题霸_牛客网
2.题目描述
描述
假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。
给定两个这种链表，请生成代表两个整数相加值的结果链表。
数据范围：0 \le n,m \le 10000000≤n,m≤1000000，链表任意值 0 \le val \le 90≤val≤9
要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。
示例1
输入：
[9,3,7],[6,3]
复制返回值：
{1,0,0,0}
复制说明：
如题面解释
示例2
输入：
[0],[6,3]
复制返回值：
{6,3}
讲解算法原理
解法：
算法思路：
模拟⾼精度加法的过程，只不过是在链表中进⾏⽽已。
编写代码
c++算法代码：
class Solution
{
public:
// 逆序链表
ListNode* reverse(ListNode* head)
{
ListNode* newHead = new ListNode(0);
ListNode* cur = head;
while(cur)
{
ListNode* next = cur->next;
cur->next = newHead->next;
newHead->next = cur;
cur = next;
}
cur = newHead->next;
delete newHead;
return cur;
}
ListNode* addInList(ListNode* head1, ListNode* head2)
{
// 1. 逆序
head1 = reverse(head1);
head2 = reverse(head2);
// 2. ⾼精度加法
int t = 0;
ListNode* cur1 = head1, *cur2 = head2;
ListNode* ret = new ListNode(0);
ListNode* prev = ret;
while(cur1 || cur2 || t)
{
if(cur1)
{
t += cur1->val;
cur1 = cur1->next;
}
if(cur2)
{
t += cur2->val;
cur2 = cur2->next;
}
prev = prev->next = new ListNode(t % 10);
t /= 10;
}
cur1 = ret->next;
ret->next = nullptr;
delete ret;
return reverse(cur1);
}
};java算法代码：
import java.util.*;
public class Solution
{
// 逆序链表
public ListNode reverse(ListNode head)
{
ListNode newHead = new ListNode(0);
ListNode cur = head;
while(cur != null)
{
ListNode next = cur.next;
cur.next = newHead.next;
newHead.next = cur;
cur = next;
}
return newHead.next;
}
public ListNode addInList (ListNode head1, ListNode head2)
{
// 1. 逆序
head1 = reverse(head1);
head2 = reverse(head2);
// 2. ⾼精度加法
ListNode cur1 = head1, cur2 = head2;
int t = 0;
ListNode ret = new ListNode(0), prev = ret;
while(cur1 != null || cur2 != null || t != 0)
{
if(cur1 != null)
{
t += cur1.val;
cur1 = cur1.next;
}
if(cur2 != null)
{
t += cur2.val;
cur2 = cur2.next;
}
prev = prev.next = new ListNode(t % 10);
t /= 10;
}
return reverse(ret.next);
}
}⼤数乘法（⾼精度乘法）
题目解析
1.题目链接：大数乘法_牛客题霸_牛客网
2.题目描述
描述
以字符串的形式读入两个数字，编写一个函数计算它们的乘积，以字符串形式返回。
数据范围： 读入的数字大小满足 0 \le n \le 10^{1000}0≤n≤101000
要求：空间复杂度 O(m)O(m)，时间复杂度 O(m^2)O(m2)（假设m是n的长度）
示例1
输入：
"11","99"
复制返回值：
"1089"
复制说明：
11*99=1089
示例2
输入：
"1","0"
复制返回值：
"0"
讲解算法原理
解法：
算法思路：
根据列竖式运算的过程模拟即可。
但是我们可以改进⼀下列竖式的过程：
▪ 先计算⽆进位相乘并且相加后的结果；
▪ 然后再处理进位。
辨析代码
c++算法代码：
class Solution
{
public:
string solve(string s, string t)
{
reverse(s.begin(), s.end());
reverse(t.begin(), t.end());
int m = s.size(), n = t.size();
vector<int> tmp(m + n);
// 1. ⽆进位相乘相加
for(int i = 0; i < m; i++)
{
for(int j = 0; j < n; j++)
{
tmp[i + j] += (s[i] - '0') * (t[j] - '0');
}
}
// 2. 处理进位
int c = 0;
string ret;
for(auto x : tmp)
{
c += x;
ret += c % 10 + '0';
c /= 10;
}
while(c)
{
ret += c % 10 + '0';
c /= 10;
}
// 3. 处理前导零
while(ret.size() > 1 && ret.back() == '0') ret.pop_back();
reverse(ret.begin(), ret.end());
return ret;
}
};java算法代码：
import java.util.*;
public class Solution
{
public String solve (String ss, String tt)
{
char[] s = new StringBuffer(ss).reverse().toString().toCharArray();
char[] t = new StringBuffer(tt).reverse().toString().toCharArray();
int m = s.length, n = t.length;
int[] tmp = new int[m + n];
// 1. ⽆进位相乘相加
for(int i = 0; i < m; i++)
{
for(int j = 0; j < n; j++)
{
tmp[i + j] += (s[i] - '0') * (t[j] - '0');
}
}
// 2. 处理进位
StringBuffer ret = new StringBuffer();
int c = 0;
for(int x : tmp)
{
c += x;
ret.append((char)(c % 10 + '0'));
c /= 10;
}
while(c != 0)
{
ret.append((char)(c % 10 + '0'));
c /= 10;
}
// 3. 处理前导零
while(ret.length() > 1 && ret.charAt(ret.length() - 1) == '0')
{
ret.deleteCharAt(ret.length() - 1);
}
return ret.reverse().toString();
}
}
