腾讯&leetcode43：字符串相乘 #105

Activity

1. sisterAn

   added

   腾讯

   on Sep 7, 2020
2. marlboroKay commented on Sep 8, 2020

   

   marlboroKay

   on Sep 8, 2020

   Last edited by marlboroKay

   More actions

   var multiply = function(num1, num2) {
     if(num1 === '0' || num2 ==='0') return '0';
     let m = num1.length, n = num2.length;
     let res = new Array(m+n).fill(0);
     for(let i = m - 1; i >= 0; i--){
       let n1 = num1[i] - '0';
       for(let j = n - 1; j >= 0; j--){
         let n2 = num2[j] - '0';
         let inSize = res[i+j+1] + n1*n2;
         res[i+j+1] = inSize % 10;
         res[i+j] += Math.floor(inSize/10)
       }
     }
     return res.join('').replace(/^0*/g, '');
   };

   👍React with 👍1Reacted by Jet
3. sisterAn commented on Sep 9, 2020

   

   sisterAn

   on Sep 9, 2020

   OwnerAuthor

   More actions

   解法一：常规解法

   从右往左遍历乘数，将乘数的每一位与被乘数相乘得到对应的结果，再将每次得到的结果累加

   另外，当乘数的每一位与被乘数高位（非最低位）相乘的时候，注意低位补 '0'

   let multiply = function(num1, num2) {
       if (num1 === "0" || num2 === "0") return "0"
       
       // 用于保存计算结果
       let res = "0"
           
       // num2 逐位与 num1 相乘
       for (let i = num2.length - 1; i >= 0; i--) {
           let carry = 0
           // 保存 num2 第i位数字与 num1 相乘的结果
           let temp = ''
           // 补 0 
           for (let j = 0; j < num2.length - 1 - i; j++) {
               temp+='0'
           }
           let n2 = num2.charAt(i) - '0'
               
           // num2 的第 i 位数字 n2 与 num1 相乘
           for (let j = num1.length - 1; j >= 0 || carry != 0; j--) {
               let n1 = j < 0 ? 0 : num1.charAt(j) - '0'
               let product = (n1 * n2 + carry) % 10
               temp += product 
               carry = Math.floor((n1 * n2 + carry) / 10)
           }
           // 将当前结果与新计算的结果求和作为新的结果
           res = addStrings(res, Array.prototype.slice.call(temp).reverse().join(""))
       }
       return res
   }
   
   let addStrings = function(num1, num2) {
       let a = num1.length, b = num2.length, result = '', tmp = 0
       while(a || b) {
           a ? tmp += +num1[--a] : ''
           b ? tmp +=  +num2[--b] : ''
           
           result = tmp % 10 + result
           if(tmp > 9) tmp = 1
           else tmp = 0
       }
       if (tmp) result = 1 + result
       return result
   }

   复杂度分析：

   • 时间复杂度：O(max(m*n , n * n))
   • 空间复杂度：O(m+n)

   解法二：竖式相乘（优化）

   两个数M和N相乘的结果可以由 M 乘上 N 的每一位数的和得到 ，如下图所示：

   

   • 计算 num1 依次乘上 num2 的每一位的和
   • 把得到的所有和按对应的位置累加在一起，就可以得到 num1 * num2 的结果

   let multiply = function(num1, num2) {
       if(num1 === '0' || num2 === '0') return "0"
       
       // 用于保存计算结果
       let res = []
       
       // 从个位数开始逐位相乘
       for(let i = 0 ; i < num1.length; i++){
           // num1 尾元素
           let tmp1 = +num1[num1.length-1-i]
           
           for(let j = 0; j < num2.length; j++){
               // num2尾元素
               let tmp2 = +num2[num2.length-1-j]
               
               // 判断结果集索引位置是否有值
               let pos = res[i+j] ? res[i+j]+tmp1*tmp2 : tmp1*tmp2
               // 赋值给当前索引位置
               res[i+j] = pos%10
               // 是否进位 这样简化res去除不必要的"0"
               pos >=10 && (res[i+j+1]=res[i+j+1] ? res[i+j+1]+Math.floor(pos/10) : Math.floor(pos/10));
           }
       }
       return res.reverse().join("");
   }

   复杂度分析：

   • 时间复杂度：O(m * n)
   • 空间复杂度：O(m + n)

   leetcode
4. Ycheck521 commented on Sep 9, 2020

   

   Ycheck521

   on Sep 9, 2020

   Last edited by Ycheck521

   More actions

   function ride(str1, str2) {
     let tempVal = 0
     let arr2 = str2.split('')
     let temp = 0
     while (arr2.length) {
       tempVal = ~~str1 * ~~arr2.pop() * factorial(temp) + tempVal
       temp +=1
     }
     return tempVal
   }
   //阶乘判断是否要补乘以10
   function factorial(n){
     if(n == 0) return 1;
     return 10*factorial(n-1)
   }
5. JohnApache commented on Apr 28, 2021

   

   JohnApache

   on Apr 28, 2021

   More actions

   没想到特别好的方法，只能用两个 for, 这个和相加，相乘和相加不一样，

   const multiplyStrings = (str1: string, str2: string) => {
       if (!str1 || !str2) return '';
       const len1 = str1.length;
       const len2 = str2.length;
       let total = 0;
       for (let i = 0; i < len1; i++) {
           const char1 = +str1.charAt(len1 - i - 1) * Math.pow(10, i);
           let multy = 0;
           let j = 0;
           for (; j < len2; j++) {
               const char2 = +str2.charAt(len2 - j - 1);
               const num = char2 * char1 + multy;
               multy = Math.floor(num / 10);
               total += (num - multy * 10) * Math.pow(10, j);
           }
           if (multy > 0) {
               total += Math.pow(10, j) * multy;
           }
       }
       return total;
   };
6. AlexZhang11 commented on May 31, 2024

   

   AlexZhang11

   on May 31, 2024

   More actions

   function getMultiply(str1,str2){
       let total = 0
       let count = 0
       for (let i =str1.length-1;i>=0;i--){
           let c = (str1.charAt(i))*1
           let s2 = str2*1
           let res = c*s2*Math.pow(10,count)
           count++
           total+=res
       }
       return total
   }
   console.log(getMultiply('2','3'))
   console.log(getMultiply("123","456"))