刷题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 hereintis.size()-1;intjt.size()-1;string ret;inttmp0;//进位数while(i0||j0||tmp){if(i0)tmp(s[i--]-0);if(j0)tmp(t[j--]-0);ret(tmp%100);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*pheadnewListNode(0);ListNode*curhead;while(cur){//头插法逆置链表ListNode*nextcur-next;cur-nextphead-next;phead-nextcur;curnext;}ListNode*retphead-next;deletephead;returnret;}ListNode*addInList(ListNode*head1,ListNode*head2){// write code herehead1reverse(head1);head2reverse(head2);inttmp0;ListNode*headnewListNode(0);while(head1!nullptr||head2!nullptr||tmp){if(head1){tmphead1-val;head1head1-next;}if(head2){tmphead2-val;head2head2-next;}intxtmp%10;ListNode*newnodenewListNode(x);newnode-nexthead-next;head-nextnewnode;tmp/10;}ListNode*rethead-next;deletehead;returnret;}};三、大数乘法题目链接大数乘法题目解析这道题就有意思了大数乘法前两道我们都是算的加法现在来看乘法给定字符串计算这两个字符串对应的乘积算法思路看到这道题多多少少还是有那么一点思路的我们还是需要模拟整个乘法的过程乘法呢我们知道一个数的每一位都要和另一个数去乘的所以这里我们使用两层for循环就可以解决问题。但是新的问题又来了那就是个位、十位和百位与另一个数乘是不一样的那乘完之后将数放到哪里呢这里定义一个vector大小是mnm和n分别表示两个字符串的长度。我们现将两个字符逆置过来这样个位所对应的下标就是0、十位就是1所以我们在计算乘的时候一个数的个位与另一个数的每一位相乘所得的积就要放在vector[ij]中什么意思呢可以看到这样我们就知道了两个数的每一位相乘需要放到哪一个位置上了。这里注意我们在第一次计算的过程中最好不要进位因为太麻烦了这里计算完成以后不进位我们遍历整个vector数组将其中的数依次进位然后转换成字符注意遍历完vector数组后可能存在进位未转换需要单独处理最后我们需要对字符串进行一个去0操作就是将最高位的0去掉再逆置一下即可代码实现classSolution{public:stringsolve(string s,string t){// write code herereverse(s.begin(),s.end());reverse(t.begin(),t.end());intms.size();intnt.size();vectorintv(mn,0);//不进位计算for(inti0;im;i){for(intj0;jn;j)v[ij](s[i]-0)*(t[j]-0);}//处理进位inttmp0;string ret;for(autoe:v){tmpe;ret(tmp%100);tmp/10;}//进位可能有余while(tmp){ret(tmp%100);tmp/10;}//对最高位进行去0while(ret.size()1ret.back()0)ret.pop_back();reverse(ret.begin(),ret.end());returnret;}};这三道高精度的算法题希望对你有所帮助感谢支持