目录
1. 大数加法
2.链表相加(二)
3.大数乘法
1. 大数加法
大数加法_牛客题霸_牛客网
算法思路：
这就是一道模拟题，模拟加法列竖式运算的过程。
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** 计算两个数之和* @param s string字符串 表示第一个整数* @param t string字符串 表示第二个整数* @return string字符串*/string solve(string s, string t) {int m = s.size() -1, n = t.size() -1;int tmp = 0;//保存进位string ret; while (m >= 0 || n >= 0 || tmp) {if(m >= 0){tmp += s[m--] - '0';}if(n >= 0){tmp += t[n--] - '0';}ret += tmp % 10 + '0';tmp /= 10;}reverse(ret.begin(), ret.end());return ret;}
};2.链表相加(二)
链表相加(二)_牛客题霸_牛客网
算法思路：
这道题与上一道题类似，只不过换成了链表，只需要注意第一步一定要先将链表逆置，其他的步骤与上一题相同。
/*** struct ListNode {* int val;* struct ListNode *next;* ListNode(int x) : val(x), next(nullptr) {}* };*/
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) {head1 = reverse(head1);head2 = reverse(head2);int tmp = 0;ListNode * cur1 = head1;ListNode * cur2 = head2;ListNode * ret = new ListNode(0);ListNode * prev = ret; while (cur1 || cur2 || tmp) {if(cur1){tmp += cur1->val;cur1 = cur1->next;}if(cur2){tmp += cur2->val;cur2 = cur2->next;}prev->next = new ListNode(tmp % 10);prev = prev->next;tmp /= 10;}prev = ret;ret = ret->next;delete prev;ret = reverse(ret);return ret;}
};3.大数乘法
大数乘法_牛客题霸_牛客网
算法思路：
同样也是一道模拟题，使用无进位相乘相加进行优化。
使用数组将每一位都存储起来，最后统一处理进位
#include <iterator>
class Solution {
public:string solve(string s, string t) {reverse(s.begin(), s.end());reverse(t.begin(), t.end());string ret;int n = s.size(), m = t.size();vector<int> v(m + n);for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){v[i + j] += (s[i] - '0') * (t[j] - '0');}}//处理进位int c = 0;for(int x : v){c += x;ret += c % 10 + '0';c /= 10;}while(c){ret += c % 10 + '0';c /= 10;}while(ret.size() > 1 && ret.back() == '0'){ret.pop_back();}reverse(ret.begin(), ret.end());return ret;}
};
