淮安市网站建设_网站建设公司_网站建设_seo优化

今天为高精度专栏，模拟不同情况下编程基础的严谨性和对边界条件处理能力。

大数加法

题目地址：大数加法

描述

以字符串的形式读入两个数字，编写一个函数计算它们的和，以字符串形式返回。

---

数据范围：s.length，t.length≤100000，字符串仅由'0'~'9'构成。

要求：时间复杂度 O(n)。

---

示例1
输入："1"，"99"
返回值："100"
说明：1+99=100

示例2
输入："114514"，""
返回值："114514"

代码展示

class Solution { public: string solve(string s, string t) { string ans; //n与m用于取对应字符串的位数 //从个位数开始相加,所以取字符串尾 int n=s.size()-1,m=t.size()-1; //temp用于处理两位相加大于10的情况 //如果相加大于10,则temp变为1并带入下一位运算 int temp = 0; //最后一次相加时,可能大于10,所以当temp不为0时再进一位 while(n>=0 || m>=0 || temp) { if(n>=0)temp += s[n--] - '0'; if(m>=0)temp += t[m--] - '0'; //取temp的个位数加入字符串ans ans += temp % 10 + '0'; //如果temp大于10,则带到下一次运算 temp /= 10; } //答案是反的,需要反转过来 reverse(ans.begin(),ans.end()); return ans; } };

链表相加（二）

题目地址：链表相加（二）

描述

假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。

给定两个这种链表，请生成代表两个整数相加值的结果链表。

数据范围：0≤n,m≤1000000，链表任意值 0≤val≤9
要求：空间复杂度 O(n)，时间复杂度 O(n)

例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。

注意事项

由于链表的特殊性，链表无法从后往前遍历，所以我们可以反转链表再进行运算，运算好后再次反转回来即为正确答案。

代码展示

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) { // write code here //cur1、cur2用于反转原链表 ListNode* cur1 = reverse(head1); ListNode* cur2 = reverse(head2); //ans用于接收相加的数 ListNode* ans = new ListNode(0); //ans用于记录头,pre用于向后操作 ListNode* pre = ans; int temp = 0; while(cur1 || cur2 || temp) { if(cur1) { temp += cur1 -> val; cur1 = cur1 -> next; } if(cur2) { temp += cur2 -> val; cur2 = cur2 -> next; } pre -> next = new ListNode(temp % 10); pre = pre -> next; temp /= 10; } //ans的头是多余的，真正的答案应该是ans->next开始 ans = reverse(ans->next); return ans; } };

大数乘法

题目地址：大数相乘

描述

以字符串的形式读入两个数字，编写一个函数计算它们的乘积，以字符串形式返回。

数据范围： 读入的数字大小满足 0≤n≤101000

要求：空间复杂度 O(m)，时间复杂度 O()（假设m是n的长度）

---

示例1

输入："11","99"

返回值："1089"

说明：11*99=1089

示例2

输入："1","0"

返回值："0"

题目解析

高精度算法题的典型题目，在高精度中，由于数字精度大到所有整数、小数类型都无法记录，则需要我们通过字符串的方式对题目进行高精度运算。

代码展示

#include <algorithm> class Solution { public: string solve(string s, string t) { // write code here reverse(s.begin(),s.end()); reverse(t.begin(),t.end()); int m=s.size(),n=t.size(); vector<int> count(n+m); //对每位数进行相乘 //相乘后不做处理，直接入vector容器里，后续再处理 for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { count[i+j] += (s[i] - '0') * (t[j] - '0'); } } //temp用于记录多余当前位数的值 int temp = 0; //ans用于记录答案 string ans; //对vector容器内数据进行处理 for(auto x : count) { temp += x; ans += temp % 10 + '0'; temp /= 10; } //temp可能还有多余的 while(temp) { ans += temp % 10 + '0'; temp /= 10; } //可能会出现字符串'00'的情况 while(ans.size()>1 && ans.back()=='0')ans.pop_back(); //答案反的 reverse(ans.begin(),ans.end()); return ans; } };

今天的学习到此结束＼＼\\٩( 'ω' )و //／／