leetcode43. 字符串相乘 经典大数+和*

43. 字符串相乘 难度中等264 给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。 示例 1: 输入: num1 = "2", num2 = "3" 输出: "6" 示例 2: 输入: num1 = "123", num2 = "456" 输出: "56088" 说明： num1 和 num2 的长度小于110。 num1 和 num2 只包含数字 0-9。 num1 和 num2 均不以零开头，除非是数字 0 本身。 不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处 在LeetCode第43题“字符串相乘”中，我们需要实现一个函数，该函数接受两个以字符串形式表示的非负整数`num1`和`num2`，并返回它们的乘积，同样以字符串形式表示。这个题目要求我们不能使用大数库，例如BigInteger，也不能直接将输入转换为整数进行计算，因此需要手动实现大数乘法的算法。 我们可以观察到，乘法的过程其实类似于小学时学习的竖式乘法。对于每个字符`num2[i]`，我们需要将其与`num1`中的所有字符进行逐位相乘，然后将结果累加到一个结果字符串`res`上。为了实现这一过程，我们可以从`num2`的最低位开始，逆序遍历每个字符。 在遍历过程中，我们需要一个变量`carry`来存储进位值，初始化为0。对于`num2`的每一位`num2[i]`，我们创建一个新的字符串`temp`用于暂时存储当前位的乘积。接着，我们对`num1`的每一位进行遍历，同时在`temp`前补0，使其长度等于`num1`的长度，这样可以确保乘法的位置正确。 在每次乘法操作中，我们获取`num1`的第`j`位字符`num1[j]`和`num2[i]`的十进制值，并将它们相加再加上`carry`的值。计算出的和`sum`取模10得到当前位的结果，然后将`sum`添加到`temp`的末尾，同时更新`carry`为商的值。遍历结束后，如果`carry`不为0，我们需要将其添加到`temp`的开头。 当处理完`num2`的所有位后，我们将`temp`反转，得到正确的乘积顺序。将`temp`拼接到结果字符串`res`的末尾，返回`res`作为最终的乘积字符串。 在这个算法中，我们使用了字符串的字符-数字转换技巧，即将字符减去字符'0'得到其对应的数值。此外，通过使用StringBuilder动态构建字符串，我们避免了不必要的字符串连接操作，提高了效率。 总结起来，解决这个问题的关键在于理解大数乘法的基本原理，以及如何在不依赖标准库的情况下实现这个过程。通过对`num2`的逆序遍历，我们可以逐位处理乘法，保证了计算的正确性。同时，通过合理利用进位`carry`和临时字符串`temp`，我们可以有效地管理中间计算结果，最终得到乘积字符串。