【practise】大数相加、大数相乘

通常，我们的int、long long类型都有最大的数字上限，也就是说再大了会有溢出问题，那么很大的数字是怎么进行运算的呢？

其中一种方法是把很大的数字转变成字符串存放到string中，然后用代码对字符串进行处理，模拟运算的过程来计算出结果的，下面介绍两道关于这方面的典型例题。

1.大数相加

大数相加练习题：LINK

是这道题目该如何去解答呢？？？

思路：模拟我们算加法的顺序

1. 先取每个字符串的最后一个字符
2. 将字符转变为数字
3. 然后运算
4. 然后写到新的字符串上去，如此循环
   图解过程：
   

实际上，这很像我们小学时候手算两个数相加的过程。
于是，我们就可以按照这个思路写出下面这种代码了：

class Solution {
public:
    string addStrings(string num1, string num2) {
        int end1 = num1.size() - 1, end2 = num2.size() - 1;
        int r1 = 0, r2 = 0;
        string retstr;
        int next = 0;
        int ret = 0;
        while(end1 >= 0 || end2 >= 0)
        {
            if(end1 >= 0)
            {
                r1 = num1[end1] - '0';
            }
            else
            {
                r1 = 0;
            }
            // r1 = end1 >= 0 ? num1[end1] = '0' : 0;

            if(end2 >= 0)
            {
                r2 = num2[end2] - '0';
            }
            else
            {
                r2 = 0;
            }
            //r2 = end2 >= 0 ? num2[end2] = '0' : 0;

            ret = (r1 + r2 + next) % 10;
            next = (r1 + r2 + next) / 10;
            retstr.push_back(ret + '0');

            end1--, end2--;
        }

        if(next == 1)
        {
            retstr.push_back('1');
        }

        reverse(retstr.begin(), retstr.end());

        return retstr;
    }
};

上面是一种性能优化代码，按照逻辑，我们每次算出的数字都需要头插的，但是头插的效率比较低，所以换成了尾插，这样到最后颠倒一下字符串的整体顺序就可以了。

2.大数相乘

与之相对的一道题目：大数相乘。
题目链接：LINK

思路：模拟乘法计算过程
乘法计算操作数只有两个，我们可以看作一个是被乘数另一个是乘数，我们只需要依次取乘数的每个数字与被乘数相乘，然后对每个数字与被乘数相乘的结果加起来就可以得出最终的结果。

class Solution {
public:
    string addStrings(string num1, string num2) {
        int end1 = num1.size() - 1, end2 = num2.size() - 1;
        int r1 = 0, r2 = 0;
        string retstr;
        int next = 0;
        int ret = 0;
        while (end1 >= 0 || end2 >= 0)
        {
            r1 = end1 >= 0 ? num1[end1] - '0' : 0;
            r2 = end2 >= 0 ? num2[end2] - '0' : 0;

            ret = (r1 + r2 + next) % 10;
            next = (r1 + r2 + next) / 10;
            retstr.push_back(ret + '0');

            end1--, end2--;
        }

        if (next == 1)
        {
            retstr.push_back('1');
        }
        reverse(retstr.begin(), retstr.end());

        return retstr;
    }

    string multiply(string num1, string num2) {
        // 1.特殊情况，乘数有0的情况
        if (num1 == "0" || num2 == "0")
        {
            return "0";
        }

        string ret = "0";
        // 2.一般情况，需要一边乘，一边加
        for (int i = num2.size() - 1; i >= 0; i--)
        {
            // 存储单个字符与一串字符相乘的结果
            string mr;
            // 补零操作
            for (int j = num2.size() - 1; j > i; j--)
            {
                mr.push_back('0');
            }
            // 拿到乘数的单个字符，并转换为数字
            int y = num2[i] - '0';
            // 依次拿到被乘数的字符，并做乘法运算
            int end1 = num1.size() - 1;
            int next = 0;
            while (end1 >= 0)
            {
                int x = num1[end1] - '0';
                int r = x * y + next;
                mr.push_back(r % 10 + '0');
                next = r / 10;

                end1--;
            }
            if (next != 0)
            {
                mr.push_back(next + '0');
            }
            // 逆转
            reverse(mr.begin(), mr.end());
            // 加值
            ret = addStrings(ret, mr);
        }

        return ret;
    }
};

好的，这两道题虽然不难但是比较有意思，可以自己写一下，当然有问题直接看力扣的题解也可以，两个题目的题解写的都很详细，还配有图片，很完美。

EOF