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

刷题day_6，继续加油哇！

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

一、大数加法

题目链接：大数加法

题目解析与解题思路

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

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

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

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

现在自己给出两个字符串1314、521；
我们来模拟一下这两个数字求和的过程

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

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

这里有两种思路：

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

这种思路也是博主在做这道题时用的思路，实现起来并不算特别麻烦；
但是有一点，需要为s、t和结果ret创建三个int类型的数组。

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

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

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

代码实现

classSolution{public:stringsolve(string s,string t){// write code hereinti=s.size()-1;intj=t.size()-1;string ret;inttmp=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());returnret;}};

二、链表相加

题目链接：链表相加

题目解析

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

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

算法思路

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

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

整体思路如下：

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

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

逆置链表：

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

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

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

代码实现

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

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

三、大数乘法

题目链接：大数乘法

题目解析

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

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

算法思路

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

乘法呢，我们知道，一个数的每一位都要和另一个数去乘的，所以这里我们使用两层for循环就可以解决问题。
但是新的问题又来了，那就是个位、十位和百位与另一个数乘是不一样的；那乘完之后将数放到哪里呢？

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

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

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

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

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

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

代码实现

classSolution{public:stringsolve(string s,string t){// write code herereverse(s.begin(),s.end());reverse(t.begin(),t.end());intm=s.size();intn=t.size();vector<int>v(m+n,0);//不进位计算for(inti=0;i<m;i++){for(intj=0;j<n;j++)v[i+j]+=(s[i]-'0')*(t[j]-'0');}//处理进位inttmp=0;string ret;for(autoe: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());returnret;}};