1.大数加法
思路：
高精度板子，停留一下都是罪过！
代码：
class Solution {
public:
string solve(string s, string t) {
vector<int> a;
vector<int> b;
for(int i=s.size()-1;i>=0;i--)a.push_back(s[i]-'0');
for(int i=t.size()-1;i>=0;i--)b.push_back(t[i]-'0');
if(s.size()==0)a.push_back(0);
if(t.size()==0)b.push_back(0);
vector<int> c;
int tt=0;
for(int i=0;i<a.size()||i<b.size();i++){
if(i<a.size())tt+=a[i];
if(i<b.size())tt+=b[i];
c.push_back(tt%10);
tt/=10;
}
if(tt)c.push_back(tt);
string ans="";
for(int i=c.size()-1;i>=0;i--){
char u=c[i]+'0';
ans+=u;
}
return ans;
}
};2.链表相加（二）
思路：
还是高精度，只不过数组换成了链表。但是换汤不换药，还是先反转一下，从低位开始加减。
在纸上画一下就好了。不过呢建议做链表题的时候多用哨兵节点，这样可以减少处理边界情况。还有就是链表题在传指针作为参数的时候，注意二级指针的问题。
代码：
#define _CRT_SECURE_NO_WARNINGS 1
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
ListNode* relist(ListNode** head) {
ListNode* a = (*head)->next;
ListNode* pre = *head;
pre->next = nullptr;
if (a == nullptr)return *head;
while (a) {
//cout<<a->val<<endl;
ListNode* temp = a->next;
a->next = pre;
pre = a;
if (temp == nullptr)break;
a = temp;
}
// cout<<a->val<<endl;
return a;
}
ListNode* addInList(ListNode* head1, ListNode* head2) {
ListNode* a = relist(&head1);
ListNode* b = relist(&head2);
ListNode* c = (ListNode*)new ListNode(-1);
ListNode* p3 = c;
ListNode* p1 = a;
ListNode* p2 = b;
int t = 0;
while (p1 || p2) {
if (p1) {
t += p1->val;
p1 = p1->next;
}
if (p2) {
t += p2->val;
p2 = p2->next;
}
ListNode* temp = (ListNode*)new ListNode(t % 10);
p3->next = temp;
p3 = temp;
t /= 10;
}
if (t) {
ListNode* temp = (ListNode*)new ListNode(t % 10);
p3->next = temp;
p3 = temp;
t /= 10;
}
return relist(&c->next);
}
};3.大数相乘
思路：
乘法高精度。比加法稍微多处理一些。两数相乘的结果最大的位数就是这两个数的位数和，比如10*100，最后的结果就是2+3=5位数。所以存答案的数组的空间开多大可以提前算出来。
模拟一下自己做乘法的过程，每次a的第i位乘以b的第j位，其结果一定在c的[i+j]位。
c此时[i+j]里有可能大于10，我们需要进位，进位就是c[i+j+1]=c[i+j]/10。进位之后再更新一下c[i+j]。
最后答案转为字符串。
值得注意的是，高精度乘法得到答案的最高位有可能不是一个一位数，比如2*10，此时的c[0]=10。这里我们用to_string就好了。
哦还有前导0的情况。为什么呢？因为我们存答案的数组c开的是理论上最大的空间，但是实际上可能不会用到这么多。比如一个一位数乘以一个一位数，最大得到一个二位数，我们就开2个int的空间。但是有可能是1*1=1还是一位数，多余的空间里存的0就是前导0.
代码：
#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
string solve(string s, string t) {
vector<int> a;
vector<int> b;
if (s == "0" || t == "0")return "0";
for (int i = s.size() - 1; i >= 0; i--)a.push_back(s[i] - '0');
for (int i = t.size() - 1; i >= 0; i--)b.push_back(t[i] - '0');
int n = a.size();
int m = b.size();
vector<int> c(m + n);
int tt = 0;
for (int i = 0; i < a.size(); i++) {
tt = 0;
for (int j = 0; j < b.size(); j++) {
tt = a[i] * b[j];
c[i + j] += tt;
// cout<<i*j<<"--"<<c[i*j]<<" ";
c[i + j + 1] += c[i + j] / 10;
c[i + j] %= 10;
}
}
int p = c.size() - 1;
while (c[p] == 0 && p >= 0) {
p--;
}
string ans = "";
for (int i = p; i >= 0; i--) {
string k = to_string(c[i]);
ans += k;
}
return ans;
}
};
