今日のアルゴリズム: 文字列の乗算

[[421393]]

この記事はWeChatの公開アカウント「3分でフロントエンドを学ぶ」から転載したもので、著者はsisterAnです。この記事を転載する場合は、「3分で学ぶフロントエンド」公式アカウントまでご連絡ください。

文字列として表される 2 つの非負整数 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 など) を使用したり、入力を直接整数に変換して処理したりすることはできません。

解決策1: 従来の解決策

乗数を右から左に走査し、乗数の各桁に被乗数を掛けて対応する結果を取得し、各回で得られた結果を累積します。

さらに、乗数の各ビットを被乗数の上位ビット（最下位ビットではない）に掛ける場合、下位ビットを「0」で埋めることに注意してください。

乗算 =関数(num1, num2) {
    if (num1 === "0" || num2 === "0" )戻り値  「0」   
     
    // 計算結果を保存するために使用されます
    res = "0"とします  
         
    // num2 は num1 とビットごとに乗算されます
(i = num2.length - 1; i >= 0; i --)の場合{  
        キャリーを0にする
        // num2 の i 番目の桁を num1 で乗算した結果を保存します
        temp = ''とします 
        // 0 で埋める
(j = 0; j < num2.length - 1 - i; j++)の場合{
温度+= '0'  
        }
        n2 = num2.charAt(i) - '0'とします。   
             
        // num2 の i 番目の桁 n2 を num1 で乗算します
( j = num1.length - 1 とします; j >= 0 || carry != 0; j --) {  
            n1 = j < 0 ? 0 とします: num1.charAt(j) - '0'  
            積を(n1 * n2 + 繰り上がり) % 10とする
温度+= 製品
            キャリー = Math.floor((n1 * n2 + キャリー) / 10)
        }
        //現在の結果と新しく計算された結果を合計して新しい結果とする
        res = addStrings(res, Array.prototype.slice.call( temp ).reverse(). join ( "" ))
    }
戻り値
} 
 
 addStrings =関数(num1, num2) {
    a = num1.length、b = num2.length、結果 = '' 、tmp = 0とします。
    while(a || b) {
        a ? tmp += +num1[ --a] : ''  
        b ? tmp += +num2[ --b] : ''   
         
        結果 = tmp % 10 + 結果
        tmp > 9 の場合 tmp = 1
それ以外の場合、 tmp = 0
    }
    if (tmp) 結果 = 1 + 結果
結果を返す
}

複雑性分析:

時間計算量: O(max(m*n, n*n))
空間計算量: O(m+n)

解決策2: 垂直乗算（最適化）

2 つの数値 M と N を乗算した結果は、次の図に示すように、M に N の各桁の合計を乗算することによって得られます。

num1 と num2 の各桁を掛け合わせた合計を計算します。
対応する位置に従ってすべての合計を加算して、num1 * num2の結果を取得します。

乗算 =関数(num1, num2) {
    if(num1 === '0' || num2 === '0' )戻り値  「0」   
     
    // 計算結果を保存するために使用されます
    res = [] とします
     
    // 一の位から桁ごとに掛け算を始める
( i = 0 とします; i < num1.length; i++){
        // num1 末尾要素
        tmp1 = +num1[num1.length-1-i]とします。 
         
 (j = 0; j < num2.length; j++)の場合{
            // num2 末尾の要素
            tmp2 = +num2[num2.length-1-j]とします。 
             
            // 結果セットのインデックス位置に値があるかどうかを判定します
            pos = res[i+j] ? res[i+j]+tmp1*tmp2 とします: tmp1*tmp2
            // 現在のインデックス位置に値を割り当てる
            res[i+j] = 位置%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));
        }
    }
 res.reverse() を返します。join ( " " ) ;
 }