青岛信息推广网站_长春城市设施建设集团股份公司_seo技术培训班_上海seo外包公司

高精度加法

大数相加

题目链接

题解

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. 处理前导0while(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];}// 处理前导0while (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、逆序打印数组