标签搜索

目 录CONTENT

文章目录

字符串乘法.md

小小城
2021-08-22 / 0 评论 / 0 点赞 / 5 阅读 / 1,065 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

字符串乘法

先看一道题
在这里插入图片描述

说明:

  1. num1 和 num2 的长度小于110。
  2. num1 和 num2 只包含数字 0-9。
  3. num1 和 num2 均不以零开头,除非是数字 0 本身。
  4. 不能使用任何标准库的大数类型(比如 BigInteger)或直接将输入转换为整数来处理

比如说我们手撕 123 × 45,应该会这样计算:

在这里插入图片描述

你看这个简单过程,其中涉及乘法进位,涉及错位相加,还涉及加法进位;而且还有一些不易察觉的问题,比如说两位数乘以两位数,结果可能是四位数,也可能是三位数,你怎么想出一个标准化的处理方式?这就是算法的魅力,如果没有计算机思维,简单的问题可能都没办法自动化处理。

首先,我们这种手撕方式还是太「高级」了,我们要再「低级」一点,123 × 5 和 123 × 4 的过程还可以进一步分解,最后再相加:
在这里插入图片描述
现在 123 并不大,如果是个很大的数字的话,是无法直接计算乘积的。我们可以用一个数组在底下接收相加结果:

在这里插入图片描述

整个计算过程大概是这样,==有两个指针 i,j 在 num1 和 num2 上游走,计算乘积,同时将乘积叠加到 res 的正确位置==

在这里插入图片描述
在这里插入图片描述

现在还有一个关键问题,如何将乘积叠加到 res 的正确位置,或者说,如何通过 i,j 计算 res 的对应索引呢?

其实,细心观察之后就发现,==num1[i] 和 num2[j] 的乘积对应的就是 res[i+j] 和 res[i+j+1] 这两个位置==

在这里插入图片描述

就可以用代码模仿出这个计算过程:

string multiply(string num1, string num2) {
    int m = num1.size(), n = num2.size();
    
    // 结果最多为 m + n 位数
    vector<int> res(m + n, 0);
    
    // 从个位数开始逐位相乘
    for (int i = m - 1; i >= 0; i--)
        for (int j = n - 1; j >= 0; j--) 
        {
            int mul = (num1[i]-'0') * (num2[j]-'0');
            
            // 乘积在 res 对应的索引位置
            int p1 = i + j, p2 = i + j + 1;
            
            // 叠加到 res 上
            int sum = mul + res[p2];//前面使用过,赋过值
            res[p2] = sum % 10;
            res[p1] += sum / 10;
        }
        
    // 结果前缀可能存的 0(未使用的位)
    int i = 0;
    while (i < res.size() && res[i] == 0)
        i++;
        
    // 将计算结果转化成字符串
    string str;
    for (; i < res.size(); i++)
        str.push_back('0' + res[i]);

    return str.size() == 0 ? "0" : str;
}
0

评论区