【C++】 —— 笔试刷题day_6

刷题day_6，继续加油哇！

今天这三道题全是高精度算法

一、大数加法

题目链接：大数加法

题目解析与解题思路

在这里插入图片描述

OK，这道题题目描述很简单，就是给我们两个字符串形式的数字，让我们计算这两个数字的和

看题目我们可以发现，题目所给的数组范围特别大，所以，我们使用int、long long肯定是不行的；

对于这种高精度算法题，我们解题思路呢也很简单，就直接模拟加法（加法竖式）就可以了。

怎么模拟呢？(这里自己给出两个数字，来模拟一下过程)

现在自己给出两个字符串1314、521；

我们来模拟一下这两个数字求和的过程

在这里插入图片描述

我们通过观察可以发现，在列竖式计算时：当前位的结果等于两个数当前位的和再加上进位数，（而进位数等于上一位的结果/10）最后再%10；

那我们就可以来模拟整个过程了：

这里有两种思路：

一就是先将字符串中的每一位转化成int并存储起来，再进行计算，最后转化成string结果返回

这种思路也是博主在做这道题时用的思路，实现起来并不算特别麻烦；

但是有一点，需要为s、t和结果ret创建三个int类型的数组。

这里就不实现这一种思路了，来看第二种思路

第二种思路也是模拟整个过程，但是不需要创建数组来存储数据，直接从字符串的最后一位开始计算，结果直接存放在ret要返回的string中，直到结束

在整个过程中，我们需要注意：

计算结果是通过push_back()尾插到结果中，所以在结果中个位是在前面的，在返回之前我们需要对其进行逆置。

代码实现

class Solution {
public:string solve(string s, string t) {// write code hereint i = s.size() - 1;int j = t.size() - 1;string ret;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;}
};

二、链表相加

题目链接：链表相加

题目解析

在这里插入图片描述

来看这一道题目，给我们两个单链表（9->3->7、6->3）每一个链表代表一个整数，让我们计算这两个链表所代表整数的和。

当然这一道题看起来和上一题类似，解法也类似，只不过多了一些链表的相关操作。

算法思路

我们通过题目给的示例可以发现，数字的最低位是在链表的结尾；

我们计算的时候都是从最低位开始计算的，所以本道题需要先将链表进行逆置再进行操作

整体思路如下：

首先将链表逆置。
再同时遍历两个逆置后的链表，计算结果，一位一位的头插到结果链表中。
最后返回结果链表即可。

这里解释一下为什么要用头插：因为我们是从个位开始计算的，而个位应该在链表的尾部，所以使用头插；就避免了使用尾插后再进行逆置链表。

逆置链表：

之前我们逆置链表是使用两个指针来逆置，这个就不多说了；

现在来看一种新的逆置方法

先定义一个链表的头节点，
再遍历原链表，将原链表的节点头插到定义的新链表中，
最后遍历结束，头结点的下一个节点就是逆置完的链表的第一个节点。

代码实现

现在来看代码实现：（当然这里也可以现将所以数取出来再进行计算）

/*** struct ListNode {*  int val;*  struct ListNode *next;*  ListNode(int x) : val(x), next(nullptr) {}* };*/
class Solution {public:ListNode* reverse(ListNode* head) {ListNode* phead = new ListNode(0);ListNode* cur = head;while (cur) {//头插法逆置链表ListNode* next = cur->next;cur->next = phead->next;phead->next = cur;cur = next;}ListNode* ret = phead->next;delete phead;return ret;}ListNode* addInList(ListNode* head1, ListNode* head2) {// write code herehead1 = reverse(head1);head2 = reverse(head2);int tmp = 0;ListNode* head = new ListNode(0);while (head1 != nullptr || head2 != nullptr || tmp) {if (head1) {tmp += head1->val;head1 = head1->next;}if (head2) {tmp += head2->val;head2 = head2->next;}int x = tmp % 10;ListNode* newnode = new ListNode(x);newnode->next = head->next;head->next = newnode;tmp /= 10;}ListNode* ret = head->next;delete head;return ret;}
};

三、大数乘法

题目链接：大数乘法

题目解析

在这里插入图片描述

这道题就有意思了，大数乘法，前两道我们都是算的加法，现在来看乘法；

给定字符串，计算这两个字符串对应的乘积；

算法思路

看到这道题，多多少少还是有那么一点思路的，我们还是需要模拟整个乘法的过程；

乘法呢，我们知道，一个数的每一位都要和另一个数去乘的，所以这里我们使用两层for循环就可以解决问题。

但是新的问题又来了，那就是个位、十位和百位与另一个数乘是不一样的；那乘完之后将数放到哪里呢？

这里定义一个vector，大小是m+n（m和n分别表示两个字符串的长度）。

我们现将两个字符逆置过来，这样个位所对应的下标就是0、十位就是1；

所以我们在计算乘的时候（一个数的个位与另一个数的每一位相乘）所得的积就要放在vector[i+j]中，什么意思呢？

在这里插入图片描述

可以看到，这样我们就知道了两个数的每一位相乘需要放到哪一个位置上了。

这里注意，我们在第一次计算的过程中最好不要进位（因为太麻烦了）

这里计算完成以后（不进位），我们遍历整个vector数组，将其中的数依次进位，然后转换成字符；
注意：遍历完vector数组后，可能存在进位未转换，需要单独处理
最后，我们需要对字符串进行一个去0操作，就是将最高位的0去掉
再逆置一下即可

代码实现

class Solution {
public:string solve(string s, string t) {// write code herereverse(s.begin(),s.end());reverse(t.begin(),t.end());int m = s.size();int n = t.size();vector<int> v(m+n,0);//不进位计算for(int i=0;i<m;i++){for(int j = 0;j<n;j++)v[i+j] += (s[i]-'0')*(t[j]-'0');}//处理进位int tmp = 0;string ret;for(auto e:v){tmp+=e;ret+=(tmp%10 + '0');tmp/=10;}//进位可能有余while(tmp){ret+=(tmp%10 + '0');tmp/=10;}//对最高位进行去0while(ret.size()>1 && ret.back()=='0')ret.pop_back();reverse(ret.begin(),ret.end());return ret;}
};