【LeetCode 43】字符串相乘 电玩女神 2022-12-16 06:06 113阅读 0赞 #### 题目描述 #### 给定两个以字符串形式表示的非负整数 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)或直接将输入转换为整数来处理。 #### 解题思路 #### 首先,对于num1和num2,如果有一个是0,那么结果就一定是0。 对于两个数的乘积,位数最多是他们两个位数的和,最少应该是比两个位数之和少1。所以,我们可以初始化一个结果数组,长度为两个数位数的和,如果最后结果的第一位是0,就直接去掉就好了。 然后,最关键的一步就是数的乘法,我们可以将每一位进行相乘,与10取余,得出的结果放在当前位,与10相除,得出的结果进到前一位。这样遍历完所有的位数,就可以实现两个字符串的相除。 时间复杂度为O(n2) #### 代码实现 #### /** * @param {string} num1 * @param {string} num2 * @return {string} */ var multiply = function(num1, num2) { if(num1 == "0" || num2 == "0") return "0" const len1 = num1.length const len2 = num2.length const res = new Array(len1 + len2).fill(0) for(let i = len1 - 1; i >= 0; i--){ const n1 = num1[i] for(let j = len2 - 1; j >= 0; j--){ const n2 = num2[j] const temp = n1 * n2 const sum = res[i + j + 1] + temp res[i + j + 1] = sum % 10 res[i + j] += sum / 10 | 0 } } while(res[0] == 0){ res.shift() } return res.join("") }; #### 提交结果 #### ![在这里插入图片描述][20201018222146705.png] [20201018222146705.png]: /images/20221123/4bae7bc48e9e47e8ad6e2d5b2e29d551.png?
还没有评论,来说两句吧...