字符串乘法计算 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：字符串乘法计算

评论礼仪 见这里，违者直接拉黑。

[NobiGo]

这个方法确实高级很多，我贴一个按照惯性思维能想到的方法：

class Solution {
    public String multiply(String num1, String num2) {
        if(num1.equals("0")||num2.equals("0")) return "0";
        String result = "0";
        for(int i = num2.length()-1;i>=0;i--){
            String value = multiplyAlong(num1,num2.charAt(i)+"");
            for(int j = i;j<num2.length()-1;j++){
                value = value+"0";
            }
            result = add(value,result);
        }
        return result;
    }
    
    
    public String multiplyAlong(String num1, String num2){
        StringBuilder stringBuilder = new StringBuilder();
        int upNumber = 0;
        int value2 = num2.charAt(0) - '0';
        for(int i = num1.length()-1;i>=0;i--){
            int value1 = num1.charAt(i)-'0';
            int value = value1*value2+upNumber;
            stringBuilder.append(value%10);
            upNumber = value/10;
        }
        if(upNumber!=0) stringBuilder.append(upNumber);
        return stringBuilder.reverse().toString();
    }
    
    
    public String add(String num1,String num2) {
        // 处理异常情况
        if(num1.equals("0")) return num2;
        if(num2.equals("0")) return num1;
        // 表示字符串的最小长度
        int maxLength = num1.length()>num2.length()?num2.length():num1.length();
        StringBuilder stringBuilder = new StringBuilder();
        int index = 0;
        int upNumber = 0;
        while(index<num1.length()&&index<num2.length()) {
            int value1 = num1.charAt(num1.length()-1-index) - '0';
            int value2 = num2.charAt(num2.length()-1-index) - '0';
            int value = value1+value2+upNumber;
            stringBuilder.append(value%10);
            upNumber = value/10;
            index++;
        }
        
        while(index<num1.length()){
            int value = upNumber + num1.charAt(num1.length()-1-index) - '0';
            stringBuilder.append(value%10);
            upNumber = value/10;
            index++;
        }
        
        while(index<num2.length()){
            int value = upNumber + num2.charAt(num2.length()-1-index) - '0';
            stringBuilder.append(value%10);
            upNumber = value/10;
            index++;
        }
        
        if(upNumber!=0) stringBuilder.append(upNumber);
        return stringBuilder.reverse().toString();
    }
}

[deepbreath373]

Java 版

class Solution {
    public String multiply(String num1, String num2) {
        int m = num1.length(), n = num2.length();
        int[] res = new int[m+n];
        for(int i = m-1; i >= 0; i--){
            for(int j = n-1; j >= 0; j--){
                int sum = (num1.charAt(i)-'0')*(num2.charAt(j)-'0');
                int p1 = i+j, p2 = i+j+1;
                sum += res[p2];
                res[p2] = sum%10;
                res[p1] += sum/10;
            }
        }
        int i = 0;
        while(i < res.length && res[i] == 0){
            i++;
        }
        StringBuilder sb = new StringBuilder();
        for(;i < res.length; i++){
            sb.append(res[i]+"");
        }
        return sb.length() == 0 ? "0" : sb.toString();
    }
}

[fornobugworld]

最后讲的太好了，我就觉得学数学跟学计算机特别矛盾，原来还是有问题的哈哈哈

[Leochens]

js版

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var multiply = function (num1, num2) {

    const m = num1.length;
    const n = num2.length;
    // m * n 最大 m+n 位
    const res = Array(m + n).fill(0);

    // 机械模拟手工计算乘法 拖式 但是更加机械
    // 使用双指针 i,j 移动位置 每一步骤都实时更新res结果 重要的是需要找到i和j在res中对应的位置

    for (let i = m - 1; i >= 0; i--) {
        for (let j = n - 1; j >= 0; j--) {
            // 获得指针对应数字相乘结果
            const mul = (+num1[i]) * (+num2[j]);
            const p1 = i + j + 1; // mul十位对应的res结果数字的索引
            const p2 = i + j;// mul个位对应的res结果数字的索引
            const sum = mul + res[p1]; // 加上之前的结果的个位
            res[p1] = sum % 10; // 个位是取余结果
            res[p2] += Math.floor(sum / 10) // 整除取十位和之前的结果相加
        }
    }
    // 完成拖式计算 要去除前导0
    let i = 0;
    while (i < res.length && res[i] == 0) i++;
    let str = res.join("").slice(i, res.length);

    return str || "0"

};

[bert82503]

打卡，感谢楼主！

[Maxiah]

感觉我好笨😥

[cathar]

Java solution with detailed comments https://leetcode.com/problems/multiply-strings/discuss/2395586/Java-beat-85-solution

1. Need to know that n1[i] * n2[j] need to be put into res[i+j] and res[i+j+1] based on observation
2. Need to add with previous calculated result, and consider carrier.

    public String multiply(String num1, String num2) {
        int m = num1.length(), n = num2.length();
        int[] res = new int[m + n];
        
        //calculate from low to high
        for(int i = m - 1; i >= 0; i--){
            for(int j = n - 1; j >= 0; j--) {
                //p2 is the lower position
                //n1[i] * n2[j] need to be put into res[i+j] and res[i+j+1]
                int hi = i + j, lo = i + j + 1;
                //new value should be added into cooresponding position of previous computation
                int mul = getDigit(num1, i) * getDigit(num2, j) + res[lo];
                res[hi] += mul / 10;
                res[lo] = mul % 10;
            }
        }
        //deal with leading 0s
        int i = 0;
        while(i < m + n && res[i] == 0) {
            i++;
        }
        
        StringBuilder sb = new StringBuilder();
        for(; i < m + n; i++) {
            sb.append(res[i]);
        }
        return sb.length() == 0 ? "0" : sb.toString();
    }
    
    private int getDigit(String s, int i) {
        return s.charAt(i) - '0';
    }

[chengrenfeng]

这个算法不用考虑进位吗？res[p1] += sum / 10;这一步需要进位怎么办？

[ShuyuanCao]

@chengrenfeng 同问

[ShuyuanCao]

@chengrenfeng 我想通了，因为第0个位置永远都是第0 + 1个位置的进位，所以第0个位置永远都是[0, 9]这个闭区间范围的。