高精度加法，高精度乘法，高精度除法，高精度减法，链表相加
文章目录
- 高精度加法
- 大数相加
- 题解
- 代码
- 高精度乘法
- 大数乘法
- 题解
- 代码
- 高精度除法
- 题解
- 代码
- 高精度减法
- 题解
- 代码
- 链表相加（二）
- 题解
- 代码
- 总结
高精度加法
大数相加
题目链接
题解
1. 可以将字符串转换为一个一个的字符相加，注意进位，从后向前加，就是你小学的计算
2. 只要存在进位，就继续加，字符串长度不同，加到长的字符串结束为止
代码
// 解法一:
class Solution
{
public:
string solve(string s, string t)
{
int a[100000] = {0},b[100000] = {0},c[100000] = {0};
int mn = 0;
int m = s.size();
int n = t.size();
mn = max(m,n);
for(int i = m-1;i >= 0;i--) a[m-1-i] = s[i] - '0';
for(int i = n-1;i >= 0;i--) b[n-1-i] = t[i] - '0';
for(int i = 0;i < mn;i++)
{
c[i] += a[i] + b[i];
c[i+1] = c[i] / 10;// 进位
c[i] %= 10;// 比如 9 + 9 = 18 % 10 = 8
}
if(c[mn]) mn++;
string p = "";
for(int i = mn-1;i >= 0;i--)
{
p += (c[i] + '0');
}
return p;
}
};
// 解法二:
class Solution
{
public:
string solve(string s, string t)
{
string ret;
int i = s.size() - 1;
int j = t.size() - 1;
int tmp = 0;// 进位
while(i >= 0 || j >= 0 || tmp)
{
if(i >= 0) tmp += s[i--] - '0';
if(j >= 0) tmp += t[j--] - '0';
ret += tmp % 10 + '0';
tmp /= 10;// 进位
}
reverse(ret.begin(),ret.end());
return ret;
}
};
高精度乘法
大数乘法
题目链接
题解
1. 无进位相乘再相加，下标在相加的位置可以得到这样的结论：下标相加相等的数，等于最后结果相加在一起，比如4和7，下标相加为1，5和6，下标相加为1，28和30都在1下标下
2. 处理进位：把个位都加入到string ret后面，进位往前加，如果最后还剩下一个进位没处理，使用while循环处理
3. 处理前导0：逆置后才是答案，所以保证数字长度大于1的前提下，如果末尾存在0就删除，比如12300->123
代码
class Solution
{
public:
string solve(string s, string t)
{
// 1.无进位相乘再相加
reverse(s.begin(),s.end());
reverse(t.begin(),t.end());
int m = s.size();
int n = t.size();
vector<int> tmp(m+n);
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. 处理前导0
while(ret.size() > 1 && ret.back() == '0') ret.pop_back();
reverse(ret.begin(),ret.end());
return ret;
}
};
高精度除法
题解
1. 高精度数除以普通整数
2. 用被除数的每一位除以除数，除完之后的余数乘10加上后面的数，除完就打印每一位数
3. 注意1234/5000和0/1的条件判断
代码
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main()
{
string s;
int b;
vector<int> ret;
cin >> s >> b;
int n = s.size();
for (int i = 0; i < n; i++) ret.push_back(s[i] - '0');
int x = 0;
bool flag = true;
for (int i = 0; i < n; i++)
{
x = x * 10 + ret[i];
// 第一个数,1234 / 5000 = 0, 0 / 1 = 0
// 只限制了第一次出现全部0的前导0,把第一次
// 出现的全部都删除了
if (flag && x / b == 0 && i < n - 1) continue;
flag = false;
cout << x / b;
x %= b;
}
cout << " ";
cout << x << '\n';
return 0;
}
高精度减法
题目链接
题解
1. 始终保证第一个数比第二个数大，如果第一个数比第二个数小，记得标记负号，交换两个数的长度和字符串保证第一个始终比第二个数大
2. 逆序存入数组a，b中，因为从低位开始减
3. 借位和存差值到c数组中
4. 记得消除前导零，消除一个零长度减一，如果都是0全消除了，记得判断长度为0时输出0并返回
5. 如果是负数记得加上负号，并且逆序输出
代码
#include<iostream>
#include<string>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N], c[N];
int main()
{
string s, t;
cin >> s >> t;
int m = s.size();
int n = t.size();
int p = m > n ? m : n;
// 判断是否有负号
int tt = 0;
if (n > m || (m == n && s.compare(t) < 0))
{
tt = 1;
swap(s, t);
swap(m, n);
}
// 倒序存储数字
for (int i = 0; i < m; i++) a[i] = s[m - i - 1] - '0';
for (int i = 0; i < n; i++) b[i] = t[n - i - 1] - '0';
// 借位 存差
for (int i = 0; i < p; i++)
{
if (a[i] < b[i])
{
a[i + 1]--;
a[i] += 10;
}
c[i] = a[i] - b[i];
}
// 处理前导0
while (p && c[p - 1] == 0) p--;
if (p == 0)
{
cout << 0 << '\n';
return 0;
}
// 加负号
if (tt)
{
cout << '-';
}
for (int i = p - 1; i >= 0; i--) cout << c[i];
cout << '\n';
return 0;
}
链表相加（二）
题目链接
题解
1. 先头插把链表进行逆序，逆序完后可以进行高精度加法，得到最终的答案
2. 注意创建一个虚拟节点更好做
代码
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution
{
public:
ListNode* Listreverse(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;
newhead = nullptr;
delete newhead;
return cur;
}
ListNode* addInList(ListNode* head1, ListNode* head2)
{
// 1.逆置,头插
ListNode* cur1 = Listreverse(head1);
ListNode* cur2 = Listreverse(head2);
// 2.高精度加法
ListNode* ret = new ListNode(0);
int t = 0;// 进位
ListNode* pre = ret;
while(cur1 || cur2 || t)
{
if(cur1)
{
t += cur1->val;
cur1 = cur1->next;
}
if(cur2)
{
t += cur2->val;
cur2 = cur2->next;
}
pre->next = new ListNode(t % 10);
pre = pre->next;
t /= 10;
}
ListNode* cur = ret->next;
ret = nullptr;
delete ret;
return Listreverse(cur);
}
};
总结
1. 高精度加减乘都是从后往前处理的，唯独高精度除法是从前往后处理的
2. 高精度减乘除法需要处理前导0，高精度加法不需要从处理前导0，比如823 + 242 -> 328 + 242 = 5601 -> 1065
3. 高精度加法逆序数组，处理进位，逆序打印，高精度减法，处理负号，逆序存储，处理借位，处理前导零，是否加负号，逆序打印数组，高精度乘法，无进位相乘再相加，处理进位，处理前导零，逆序打印，高精度除法，每次处理商，处理余数，处理前导零
4. 基本的做题步骤：
1、将数组逆置
2、处理进位/借位
3、处理前导零
4、逆序打印数组