【刷题汇总--大数加法、 链表相加(二)、大数乘法】

今日刷题汇总 - day006

1、大数加法

1.1、题目

1.2、思路

读完题,明白大数相加,通常采用字符串的模式,是为了解决int等类型大数相加超出范围的应用, 那么让思考模拟实现数字字符串的加法运算. 那么,要实现加法运算,很快能想到将字符串的每一位都转为数字计算求和,最后再转回字符串返回不就行了吗? 那么,需要求得两个字符串的长度len1和len2,然后同样采用预处理,一位一位的处理,即个位相加,所以定义一个变量carry表示个位相加后的进位,定义一个变量sum表示个位上的和,那么求sum的个位就是需要返回的字符串retstr的个位数字了.依次循环直到len1和len2都计算结束后,得到了累加和的retstr字符串,但是我们直接尾插属于是得到的逆置的结果,而需要的结果是需要正序的,所以还可以利用reverse逆置retstr字符串才是我们需要的结果.此外,在逆置之前,我们还需要判断,最后进位上是否已经加上(如示例1的情况),如果没加则继续尾插字符’1’ ,否则,直接逆置即可.接下来,就是程序实现.

1.3、程序实现

首先,根据思路,求得len1和len2两个数字字符串的长度, 然后定义retstr最后要返回的字符串,继续定义进位变量carry, 定义sum个位上的和,定义尾插到retstr的个位结果数individual变量.

#include <iterator>
class Solution {
public:string solve(string s, string t){int len1 = s.size()- 1;int len2 = t.size() -1;string retstr;retstr.reserve(len1 > len2 ? len1 + 2:len2 + 2);int carry = 0;int sum = 0;int individual = 0;return retstr;}
};

接着,处理数字字符串的相加,思考不难知道while的条件是需要一直处理到较长字符串结束才行,所以需用 | | 运算,然后,分别转换两个字符串的个位字符为数字,保存到变量value1和value2中,然后求和得到sum,注意记得加上carry才行(因为循环第二趟,如果sum不加上进位是计算不正确的哈),然后将求到的sum十位数字保存在carry就是个位求和所得的进位,同理,求sum的个位individual 就是需要尾插到retstr的返回结果的数字,依次类推,直到两个字符串全部加完,这里巧妙的使用三目运算符解决较短字符串加完后,长字符串继续加时,短字符串累加就是置为0进行相加. 此外, 注意字符元素 - '0’转化为数字,尾插时需要individual + ‘0’转回字符.最后,判断一下进位是否为空,否则继续尾插一个字符’ 1’即可.由于retstr是尾插操作,所以我们需要的结果,利用reverse逆置一下再返回结果即可.

#include <iterator>
class Solution {
public:string solve(string s, string t){int len1 = s.size()- 1;int len2 = t.size() -1;string retstr;int carry = 0;int sum = 0;int individual = 0;while(len1 >= 0 || len2 >= 0){int value1 = len1 >= 0 ? s[len1--] - '0' : 0;int value2 = len2 >= 0 ? t[len2--] - '0' : 0;sum = value1 + value2 + carry;carry = sum /10 ;individual = sum % 10;retstr += individual + '0';}if(carry){retstr += '1';}reverse(retstr.begin(),retstr.end());return retstr;}
};

此外,还能够利用reserve提前开辟好空间.

#include <iterator>
class Solution {
public:string solve(string s, string t){int len1 = s.size()- 1;int len2 = t.size() -1;string retstr;retstr.reserve(len1 > len2 ? len1 + 2:len2 + 2);int carry = 0;int sum = 0;int individual = 0;while(len1 >= 0 || len2 >= 0){int value1 = len1 >= 0 ? s[len1--] - '0' : 0;int value2 = len2 >= 0 ? t[len2--] - '0' : 0;sum = value1 + value2 + carry;carry = sum /10 ;individual = sum % 10;retstr += individual + '0';}if(carry){retstr += '1';}reverse(retstr.begin(),retstr.end());return retstr;}
};

2、 链表相加(二)

2.1、题目

2.2、思路

读完题, 知道跟上道题类似的,只不过要求让我们利用链表完成数字的加法运算. 然后返回运算完成后的链表,注意的是这里是单链表,而加法是从低位向高位作加法运算的.不过不像上道题可以调用库中封装好的reverse, 所以得想办法自己写一个逆置链表的函数,逆置后再用带头的链表retListhead 作为返回结果的链表和工作指针retcur 模拟头插, 循环实现个位上的加法求和sum, 再依然像上道题一样采用进位和头插个位individual到retListhead 链表中, 其中值得注意的是,利用带头的链表方便操作,所以不管是逆置操作还是最后返回结果链表之前都需要释放头结点,从第一个节点处返回即可.那么接下来,就是程序实现.

2.3、程序实现

首先,按照题目思路分析的需求,封装一个逆置函数reverse, 那么为了方便使用带头的链表newhead ,然后利用cur工作指针遍历需要逆置的链表, 遍历一个头插一个到newhead即可, 因为是链表的常规操作,只需要注意一下最后返回前释放头结点, 返回第一个节点处,另外就是利用nextnode保留原链表的下一个节点,否则cur回不去原链表继续遍历, 且注意链表的指向顺序, 由于是单链表所以先改后面的指向再改前面的指向,否则先改前面的指向会导致自己指向自己就属于无用功,错误操作了.为了方便理解,简单画个图:

/*** 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* nextnode = cur->next;cur->next = newhead->next;newhead->next = cur;cur = nextnode;}cur = newhead->next;delete newhead;return cur;}ListNode* addInList(ListNode* head1, ListNode* head2){head1 = reverse(head1);head2 = reverse(head2);}
};

完成了逆置链表, 就像上道题一样需要知道链表的长度, 这里利用cur1和cur2工作指针,直到较长的链表加完为止,所以用 || 运算, 接着定义需要返回的链表retListhead和它的工作指针retcur, 为了方便头插所以使用的带头的,最后释放掉就行了, 然后定义sum这里用于求和和进位控制, 由于是个位一位一位的作加法运算,所以sum/=10就是得到的进位, 一起放入while进行或运算, 有进位就再头插一次即可, 接着就是跟上道题没什么区别的逻辑了.写好函数体,最后释放头结点,将返回的链表逆置后返回即可.

/*** 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* nextnode = cur->next;cur->next = newhead->next;newhead->next = cur;cur = nextnode;}cur = newhead->next;delete newhead;return cur;}ListNode* addInList(ListNode* head1, ListNode* head2){head1 = reverse(head1);head2 = reverse(head2);ListNode* cur1 = head1;ListNode* cur2 = head2;ListNode* retListhead = new ListNode(0);ListNode* retcur = retListhead;int sum = 0;int individual = 0;while(cur1 || cur2 || sum){if(cur1){sum += cur1->val;cur1 = cur1->next;}if(cur2){sum += cur2->val;cur2 = cur2->next;}individual = sum % 10;retcur = retcur->next = new ListNode(individual);sum /= 10;}retcur = retListhead->next;retListhead->next = nullptr;delete retListhead;retcur = reverse(retcur);return retcur;}
};

3、大数乘法

3.1、题目

3.2、思路

读完题,知道这类题也跟第一题一样属于解决数值太大超出范围时的一种应用题型. 让我们实现用数字字符串模拟乘法的效果, 并以字符串的形式返回即可. 那么,说着是乘法, 肯定要以化繁为简的思想去思考, 通过推导和验证发现, 可以把乘法换算成加法的运算,具体可以画个图演示一下:

首先根据示意图可以看出:
(1). 字符串的下标是逆置的,作运算需要先逆置;
(2). 依次相乘后, 结果行result等于绿色加蓝色;
(3). 然后对结果行的高位作为进位, 对结果行取模得到的个位数作为最后的结果返回即可.
其次, 结果数组result的大小最大是两个字符串的长度之和,如上图就是3+2 = 5, 即 result[m+n] .另外还需要注意题目中示例2具有前导0的情况, 那么接下来就是程序实现.

3.3、程序实现

首先根据思路的分析程序就大致分为以下几步:
(1). 逆置字符串和求字符串长度为运算和确定reslut数组做准备;
(2). 开辟result结果求和数组,并套两层for循环求得结果放入数组中,注意此时数组得到的结果仍然是逆置的;
(3). 处理结果数组中的个位进行尾插与十位进位的问题;
(4). 处理前导0的情况;
(5). 最后逆置retstr字符串返回即可.

那么先逆置字符串, 才好进行运算.再求字符串的长度,保存到变量m和n, 然后就可以确定开辟结果数组result的大小了, 然后,按照思路分析的蓝色和绿色进行相乘求和运算保存到result数组中.为了好理解还是在之前图的例子中, 画个图理解result[i+j]的作用:

#include <algorithm>
class Solution
{
public:string solve(string s, string t){reverse(s.begin(),s.end());reverse(t.begin(),t.end());int m = s.size();int n = t.size();vector<int> result(m+n);for(int i = 0;i < m;i++){for(int j = 0; j < n;j++){result[i+j] += (s[i] - '0')*(t[j] - '0');}}}
};

接着, 处理结果数组中的个位进行尾插与十位进位的问题;先定义一个变量carry表示进位,再定义一个restr需要返回的字符串,准备进行尾插, 然后遍历数组执行取模即个位进行尾插即可,套路跟前两道题都类似,只是要注意遍历结束后由于还可能存在进位的数未处理,如上图中的最高位2,需要额外判断再尾插进去即可.

#include <algorithm>
class Solution
{
public:string solve(string s, string t){reverse(s.begin(),s.end());reverse(t.begin(),t.end());int m = s.size();int n = t.size();vector<int> result(m+n);for(int i = 0;i < m;i++){for(int j = 0; j < n;j++){result[i+j] += (s[i] - '0')*(t[j] - '0');}}int carry = 0;string retstr;for(auto ch : result){carry += ch;retstr += carry%10 + '0';carry /= 10;}while(carry){retstr += carry%10 + '0';carry /= 10;}}
};

最后,就是处理前导0的情况,且保存末尾的0,值得注意的是因为是逆置所以判断是判断尾巴即back处的字符,然后pop掉多余的0,然后逆置retstr字符串返回即可.

#include <algorithm>
class Solution
{
public:string solve(string s, string t){reverse(s.begin(),s.end());reverse(t.begin(),t.end());int m = s.size();int n = t.size();vector<int> result(m+n);for(int i = 0;i < m;i++){for(int j = 0; j < n;j++){result[i+j] += (s[i] - '0')*(t[j] - '0');}}int carry = 0;string retstr;for(auto ch : result){carry += ch;retstr += carry%10 + '0';carry /= 10;}while(carry){retstr += carry%10 + '0';carry /= 10;}while(retstr.size() > 1 && retstr.back() == '0'){retstr.pop_back();}reverse(retstr.begin(), retstr.end());return retstr;}
};

4、题目链接

大数加法
链表相加(二)
大数乘法