【算法手记6】NC1 大数加法 && NC40 链表相加(二) && NC10 大数乘法

修修修也

发布于 2025-03-29 09:31:09

3600

代码可运行

文章被收录于专栏：修也的进阶日记修也的进阶日记

运行总次数：0

代码可运行

一.NC1 大数加法

牛客网题目链接(点击即可跳转):NC1 大数加法

题目详情:

本题详情如下图:

题目思路:

本题解题思路如下: 模拟小学列竖式加法即可,但是要注意进位和两个字符串的处理,可以写成一个循环逻辑走完的就不要分两步分多种情况讨论了.对情况的处理要尽量泛化,不要只思考到局部的情况就单拎出来写一个模块,实际上是存在共性的,多思考共性,会让代码和思路都简单不少. 步骤越繁琐越容易出错,并且越不容易找到问题在哪里.

解题代码:

本题解题代码如下:

class Solution 
{
public:
    string solve(string s, string t) 
    {
        string ret;

        int i=s.size()-1,j=t.size()-1;
        int tmp = 0;
        while(i>=0 || j>=0 || tmp)  //任意一个不为0就一直加
        {
            if(i>=0) tmp +=s[i]-'0';
            if(j>=0) tmp +=t[j]-'0';
            ret+=(tmp%10+'0');
            tmp/=10;
            i--;
            j--;
        }
        reverse(ret.begin(),ret.end());
        return ret;
    }
};

二.NC40 链表相加(二)

牛客网题目链接(点击即可跳转):NC40 链表相加(二)

题目详情:

本题详情如下图:

题目思路:

本题解题思路如下: 本题解题我们要思考如何取链表尾部的数据逐一相加. 因为大数加法的底层逻辑都是类似于上面一题那样模拟小学列竖式算加法, 但是对于链表而言每次取尾部的结点非常麻烦,那自然我们就想到需要先将链表逆序一下,然后再参照大数相加的方法相加. 所以本题解题步骤分为两步, 首先将两个相加链表逆置, 然后逐一取下结点相加,相加的结果结点再头插到返回的链表中(这样保证返回的链表是正序,或者尾插进去再逆置也是可以的).

解题代码:

本题解题代码如下:

#include <algorithm>
class Solution 
{
public:
    //链表逆序
    ListNode* reverse(ListNode* head)
    {
        ListNode* newHead = new ListNode(0);
        ListNode* cur = head;
        while(cur!=nullptr)
        {
            //头插cur结点进newHead
            ListNode* tmp = cur->next;
            cur->next=newHead->next;
            newHead->next=cur;
            cur=tmp;
        }
        return newHead->next;
    }
    ListNode* addInList(ListNode* head1, ListNode* head2) 
    {
        ListNode* ret = new ListNode(0);
        //难点在找尾,那逆序不就好了^_^
        head1=reverse(head1);
        head2=reverse(head2);
        ListNode* cur3 = ret;
        //相加逻辑
        int tmp=0;

        while(head1!=nullptr||head2!=nullptr||tmp)
        {
            if(head1!=nullptr)
            {
                tmp+=head1->val;
                head1=head1->next;
            }
            if(head2!=nullptr)
            {
                tmp+=head2->val;
                head2=head2->next;
            }
            //结果结点头插进新链表
            ListNode* newnode = new ListNode(tmp%10);
            newnode->next=cur3->next;
            cur3->next=newnode;
            tmp/=10;
        }
        return ret->next;
    }
};

三.NC10 大数乘法

牛客网题目链接(点击即可跳转):NC10 大数乘法

题目详情:

本题详情如下图:

题目思路:

本题解题思路如下: 我们先用无进位相乘分别算出每一位数字相乘后的结果,将他们同位的值相加,然后最后再把无进位相乘的结果汇总为一个字符串,返回即可(注意返回前消灭前导0),具体看下图:

解题代码:

本题解题代码如下:

class Solution 
{
public:
    string solve(string s, string t) 
    {
        string ret;
        
        //无进位相乘
        vector<int> tmp;
        tmp.resize(s.size()+t.size(),0);
        for(int i=s.size()-1;i>=0;i--)
        {
            for(int j=t.size()-1;j>=0;j--)
            {
                tmp[i+j]+=(s[i]-'0')*(t[j]-'0');
            }
        }
        //把每位乘的汇总相加,乘完是逆序的哈
        int c=0;
        int i=tmp.size()-1;
        while(i>=0||c)
        {
            if(i>=0) c+=tmp[i];
            ret+=(c%10+'0');
            c=c/10;
            i--;
        }
        //消灭前导零
        while(ret[0]=='0' && ret.size()>1)
        {
            ret.erase(ret.begin());
        }  
        reverse(ret.begin(),ret.end());
        return ret;
    }
};