9、字符串相加

接下去的两道可能会比较复杂一些，因为涉及字符串的加减乘除

① 题目描述：

② 思路分析：

可以看到，题目的意思很简单，就是将两个字符串看做数值进行相加，但是呢最后又是两个字符串，那这怎么搞呢？很多同学一时半会没辙了
这里的话就要涉及到字符串的分割技术了。因两个数在相加的时候是需要从个位开始相加，所以我们肯定要把两个字符串中的的位数一个一个地取出来，将它们都转换为数值之后再进行相加，每一位上的数都是如此

但是呢，上面这一种只是普通的情况，我们来看看下面这一种，虽然也是各个位上的数进行相加，但是呢出现了进位的情况，加法进位相信大家在小学阶段就已经学过了，不过呢这个进位要如何进行处理，每个位上的数字要如何进行拼接，且听我娓娓道来:tea:

这里我们也是采取的双指针的思路，这么做下来的话你应该可以发现【双指针】在字符串的题目中出现的还是非常频繁的，所以我们要掌握这一快，在做题的时候才能事半而功倍

让这两个指针分别从末尾开始即可

int end1 = num1.size() - 1;
int end2 = num2.size() - 1;

然后我们要想办法获取到这个位置上的字符，然后将其转换为数值的形式，这里使用到了三目运算符，主要是判断这个指针是否到达最前端的情况

// 首先获取到两个字符串的尾数
int val1 = end1 >= 0 ? num1[end1] - '0' : 0;
int val2 = end2 >= 0 ? num2[end2] - '0' : 0;

接下去我们就可以去累加这个两个数了，这个carry呢就是我们上面所说的进制，一开始无需理会，因为一定是为0的，然后在下面继续更新这个进制位

int ret = val1 + val2 + carry;

对于这个进制位和这一位上的值呢，我们可以这么去更新

// 更新进位值
carry = ret / 10;
// 取出当前位上的余数
ret %= 10;

具体的话还是看图示吧 ⇒ 很清楚，如果我们要取到这个进制位1的话，就需要让这个ret / 10，如果我们需要取到这个除进制位外的余数的话，就需要让ret %= 10才能取得到

那当我们有这个位上的数值后，就可以将其加入到retStr中了，不过呢这还是一个数值，我们还要将其转换为字符才可，+ '0'即可

// 累加到新的string对象中去(尾插)
retStr += (ret + '0');

然后别忘了前移这两个指针，因为我们还要去计算下一位

end1--;
end2--;

最后的话再来写一下循环结束的条件，很多同学都给出end1 >= 0 && end2 >= 0，但是这可行吗？我们知道循环的条件是继续的条件，对于逻辑与&&来说只有表达式两边都为真的时候才为真，那么当有一个为假的时候就不对了。
那么当一个字符串遍历结束后我们就结束相加吗？

while(end1 >= 0 || end2 >= 0)

我们来看一下这个案例就可以了，【999 + 1 = 1000】，如果我们执行完【9 + 1 = 10】后就结束了，那么最后返回的就是0了，这很明显是不符合实际的。那么当一个结束了之后还不能结束我们需要使用的是 按位或||

然后我们就返回这个retStr去执行一下吧，但是先计算的结果刚好反了

如果对 string类 中的operator+=()接口了解的话就可以清楚我们这里其实是做了一个尾插的操作，所以这个顺序才会是倒着的，那我们要获取到正确的顺序的话采取reverse()做一个颠倒即可

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

这回再去执行的话确实是没什么问题了，但是呢提交之后可以发现，有一些测试用例的话我们是跑不过（示例能跑过不代表所有测试用例都能跑过）

这个测试用例其实大家可以带入到我们上面的这个循环中，就发现它跑完一遍的话就结束了，因为位数只有一位，那么此时我们在循环结束之后应该再去做一个判断才行，如果这个进制位不为0的话（正常结束进制位一定为0），我们就要再把这个进制位给追加上去

// 如果在出了循环后carry为1的话, 则表示二者只有1位的长度
if(carry == 1)  
{
    retStr += '1';
}

③ 代码展示：

然后展示一下，读者最好自己去推导一遍然后尝试着写写看

class Solution {
public:
    string addStrings(string num1, string num2) {
        int end1 = num1.size() - 1;
        int end2 = num2.size() - 1;
        string retStr;
        int carry = 0;      // 进位值
        // 一个结束之后还不能结束
        while(end1 >= 0 || end2 >= 0)
        {
            // 首先获取到两个字符串的尾数
            int val1 = end1 >= 0 ? num1[end1] - '0' : 0;
            int val2 = end2 >= 0 ? num2[end2] - '0' : 0;
            // 累加当前位置上的数字
            int ret = val1 + val2 + carry;
            // 更新进位值
            carry = ret / 10;
            // 取出当前位上的余数
            ret %= 10;
            // 累加到新的string对象中去(尾插)
            retStr += (ret + '0');
            end1--;
            end2--;
        }
        // 如果在出了循环后carry为1的话, 则表示二者只有1位的长度
        if(carry == 1)  
        {
            retStr += '1';
        }
        // 最后再对尾插后的字符串做一个翻转
        reverse(retStr.begin(), retStr.end());
        return retStr;
    }
};

④ 运行结果：

来看看执行结果，发现效率中一般，不过能AC就行😁

10、字符串相乘【⭐⭐】

看完了 字符串相加 后，我们再来看 字符串相乘，本题要在上一题的基础上难很多，做好准备，发车了:car:

① 题目描述：

力扣原题

class Solution {
public:
    string multiply(string num1, string num2) {
    }
};

② 思路分析：

题目意思也是一样很简单，把两个字符串当成数值一样来进行相乘，最后返回的结果还是一个 字符串。我们知道对于乘法而言和加法不同，对于加法而言我们只需要考虑一个进位的问题，但是对于乘法而言不一样，我们要考虑的则是更多
通过下面来看，两个三位数相乘的话我们要考虑让上面的那个数和下面的每个数进行相乘，并要把它们加起来，不过在相加的时候也需要再考虑到的时我们要实行的是【错位相加】，什么意思呢？

例如下面的这个738不能直接和615进行相加，而是要和6150进行相加，因为这是上面的数与十位数【5】相乘所得的结果，那么下面也是一样，我们要和49200进行相加

代码走读🏃‍

💬 经过上面这么一分析，相信你一定觉得这个题目要考虑的因素有很多了。不用怕，我们立马来进行分析

首先我们考虑一下特殊情况，若是这个num1或者是num2存在字符0相同的话，那不需要再进行相乘了，因为任何数与0相乘一定为0，那么我们直接返回“0”

if(num1 == "0" || num2 == "0")
    return "0";

💬 接下去我们要明确的一点是，我们要让那些数进行相乘？要乘几次？

很明显这里的num1为被乘数，num2是每一位乘数，它有几位我们就需要乘几次，所以我们这里拿【sz1】和【sz2】分别去做一个记录

int sz1 = num1.size();      // 被乘数
int sz2 = num2.size();      // 次数

上面说到这个num2的位数即为需要相乘的次数，那我们在这里给到的外层循环就是去遍历这个sz2的大小

for(int i = sz2 - 1; i >= 0; --i)
{
  // ...
}

下面有两个string类的对象，ans表示最后累加总和后所需要存放的字符串；curr则表示我们每乘完一次构后所需要累加到字符串

string ans = "0";

string curr = "";

下面这段逻辑非常地重要，看着代码本身大家应该就可以知道，就是我们在上面所说到的。如果被乘数和十位或者百位上的数相乘的话，若是在后面和总数进行相加的时候就需要对应地添上0

// 给此处其余位添加0
for(int j = sz2 - 1; j > i; --j){
    curr.push_back(0 + '0');
}

那接下去呢我们就可以去获取到对应的字符，然后将它们转化为数值进行运算了

下面这一段代表的就是被乘数与其中一位的乘数进行相乘的逻辑，这个[y]指的就是num2中的那一位乘数，而[x]则指的是通过循环获取到的每一位被乘数，二者的乘积还要再加上进制位，因为乘法和加法一定也会产生进制位，那么接下去两句在更新 当位结果和 进制位 的时候，读者就不会那么生疏了
那随着循环的一步步进行，num2中当前的这一位乘数和被乘数就计算出了结果

int carry = 0;      // 进制位 
int ret = 0;
// 开始逐位累乘
int y = num2[i] - '0';      // 获取到当前这一位的数值
for(int k = sz1 - 1;k >= 0; --k)
{
    int x = num1[k] - '0';   // 获取到被乘数的数值位
    ret = x * y + carry;
    curr.push_back(ret % 10 + '0');
    carry = ret / 10;        // 更新进制位
}

当然，和我们上一题中所考虑到的一样，对于乘法来说也会存在两个个位数的情况，如果此时因为循环只执行了一次的话，那还有一个位数一定没有被累加进来，此时我们就需要再把它拿过来

// 考虑到个位数的问题
if(carry != 0){
    curr.push_back(carry % 10 + '0');
    carry /= 10;
}

我们可以到VS下来测试一下这种情况，可以看到当这个num1和num2都为个位数的时候，它们在相乘时只会进入一次循环，此时可以看到这个carry是为3的，因此还会再进入下面的那个if判断，将其追加到【curr】中

最后的话别忘记了我们是使用的push_back()即尾插，那里面的字符串都是颠倒的，还要调用一下reverse()函数去做一个反转

// 翻转字符串
reverse(curr.begin(), curr.end());

当然对于上面的这段逻辑只是被乘数与一个乘数之间的计算结果，我们要的是所有的结果之和

可再看一下下图思考思考

这里我们还需要一个字符串相加的逻辑，那其实的话就是我们在上面做到的那题

// 累加每一个计算完后的字符串
ans = AddStrings(ans, curr);

③ 整体代码展示：

class Solution {
public:
    string multiply(string num1, string num2) {
        if(num1 == "0" || num2 == "0")
            return "0";
        int sz1 = num1.size();      // 被乘数
        int sz2 = num2.size();      // 次数
        string ans = "0";
        // 外层遍历次数
        for(int i = sz2 - 1; i >= 0; --i)
        {
            string curr = "";
            // 给此处其余位添加0
            for(int j = sz2 - 1; j > i; --j){
                curr.push_back(0 + '0');
            }
            int carry = 0;      // 进制位 
            int ret = 0;
            // 开始逐位累乘
            int y = num2[i] - '0';      // 获取到当前这一位的数值
            for(int k = sz1 - 1;k >= 0; --k)
            {
                int x = num1[k] - '0';   // 获取到被乘数的数值位
                ret = x * y + carry;
                curr.push_back(ret % 10 + '0');
                carry = ret / 10;        // 更新进制位
            }
            // 考虑到个位数的问题
            if(carry != 0){
                curr.push_back(carry % 10 + '0');
                carry /= 10;
            }
            // 翻转字符串
            reverse(curr.begin(), curr.end());
            // 累加每一个计算完后的字符串
            ans = AddStrings(ans, curr);
        }
        return ans;
    }
    // 两个字符串相加逻辑
    string AddStrings(string& num1, string& num2)
    {
        int end1 = num1.size() - 1;
        int end2 = num2.size() - 1;
        int ret = 0;
        int carry = 0;
        string retStr;
        while(end1 >= 0 || end2 >= 0 || carry != 0)
        {
            int val1 = end1 >= 0 ? num1[end1] - '0' : 0; 
            int val2 = end2 >= 0 ? num2[end2] - '0' : 0;
            ret = val1 + val2 + carry;
            carry = ret / 10;
            retStr += ret % 10 + '0';
            end1--;
            end2--;
        }
        reverse(retStr.begin(), retStr.end());
        return retStr;
    }
};

调试观察💻

经过上面的代码走读，相信读者已经明白了一些原理，但是呢心中一定感觉还有些含糊。接下去我将会带着你一步步地去做调试，来看看这段代码究竟是如何

我们就以本文所讲的这个【123】和【456】带读者来看看

我们通过动图来观察，此时第一次进入循环，即要拿被乘数123和第一个乘数位4进行计算，此时呢我们是无需添加0的，所以这里的循环不进入是对的，记住这边的这个循环的结束条件是j < i，而不是j <= i，否则在第一次进入循环的时候就会多出来一个0了（博主在这里踩过坑，希望读者注意！！）