字符串乘法计算 :: 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();
    }
}

[tiandee]

好复杂，面试时可能没有这么多时间写这么久

[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();
    }
}

[Dongyu1126]

感谢，写的很棒，对新手很友好

[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;这一步需要进位怎么办？

[kennethahah]

进位的事情会由下一次循环的时候处理，最后得出的结果是进位过的，但是中间过程res的某一个位置可能出现超过9的数。
你也可以在res[p1] += sum//10的时候加入下面这串代码，
while result[p1] >= 10:
res[p1-1] += res[p1]//10
res[p1] = res[p1]%10
p1 -= 1
就可以让他在中间过程的时候res里的数字也是合法的了。
（但是没必要这么搞）

[ShuyuanCao]

@chengrenfeng 同问

[ShuyuanCao]

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

[linhr11]

没想到还能用数组，真的没想到
public String multiply(String num1, String num2) {
int[] sum = new int[num1.length() + num2.length()];
StringBuilder res = new StringBuilder();
boolean flag = false;

    for (int i = num2.length() - 1; i >= 0 ; i--) {
        for (int j = num1.length()-1; j >= 0; j--) {
            int re = (num1.charAt(j) - '0') * (num2.charAt(i) - '0') ;
            re += sum[i+j+1];
            sum[i+j] += re/10;
            sum[i+j+1] = re%10;
        }
    }

    for (int emus: sum
    ) {
        if (emus == 0 && !flag){
            continue;
        }

        if (emus != 0){
            flag = true;
        }

        res.append(emus);
    }

    return res.length() == 0 ? "0" : res.toString();
}

[mghio]

Rust 版本：

pub fn multiply(num1: String, num2: String) -> String {
    let m = num1.len();
    let n = num2.len();
    let mut res = vec![0; m + n];

    for i in (0..m).rev() {
        for j in (0..n).rev() {
            let mul = (num1.as_bytes()[i] - b'0') * (num2.as_bytes()[j] - b'0');
            let p1 = i + j;
            let p2 = i + j + 1;

            // 使用位运算代替除法
            let carry = (mul >> 10) & 1;
            res[p2] += mul % 10 + carry;
            res[p1] += carry;
        }
    }

    let mut carry = 0;
    let mut result = String::new();
    for i in (0..res.len()).rev() {
        let sum = res[i] + carry;
        result.push(sum % 10 as char);
        carry = sum / 10;
    }

    // 删除任何前导零
    while result.len() > 1 && result.chars().next().unwrap() == '0' {
        result.pop();
    }

    result
}

[shiboys]

我也贴一个受到 leetcode 第 2 题的链表实现加法的启发，这里实现一个链表实现乘法的方式

public String multiply(String num1, String num2) {
        /**
         * 前提条件是不允许使用 BigInteger，也不能把输入的字符串转换成整数
          *链表是实现两数之积。
         * 思路是将 num1 中的每个字符 乘以 nums2 得到一个链表，
         * 最终形成一个链表数组，然后合并链表数组为一个链表
         * 用 StringBuilder 将链表中的数据全部取出，然后反转返回
         * 也可以递归遍历链表，用后序的方式取出链表中的元素
         */
        if (num1 == null || num1.isEmpty() || num2 == null || num2.isEmpty()) {
            throw new IllegalArgumentException();
        }
        ListNode[] heads = new ListNode[num2.length()];
        ListNode headb = getListNodeFromString(num1);
        int n = num2.length();
        for (int i = 0; i < n; i++) {
            // 获取当前字符跟 nums1 的链表的乘积后的链表
            heads[i] = getMultiplyBySingleListNode(headb, num2.charAt(i), n - 1 - i);
        }
        // 将所有的链表相加
        ListNode head = getMultiLinkedListSum(heads);
        StringBuilder sb = new StringBuilder();
        ListNode p = head;

        while (p != null) {
            sb.append(p.val);
            p = p.next;
        }
        String s = sb.reverse().toString();
       // 处理以 '0' 开头的字符
        if (s != null && s.length() > 0 && s.startsWith("0")) {
            int idx = 0;
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) > '0') {
                    idx = i;
                    break;
                }
            }
            s = s.substring(idx);
        }
        return s;
    }

    /**
     * 将字符串转换成链表。
     * 123=> 3-2-1
     * 
     */
    private ListNode getListNodeFromString(String val) {
        ListNode listNode = null;
        char[] chs = val.toCharArray();
        for (char ch : chs) {
            listNode = new ListNode(ch - '0', listNode);
        }
        return listNode;
    }

    /**
     * 链表乘以单个字符
     * 
     * @param head1
     * @param ch       当前乘以的字符
     * @param zeroNums 需要前面补 0 的个数
     * @return
     */
    ListNode getMultiplyBySingleListNode(ListNode head1, char ch, int zeroNums) {
        ListNode dummy = new ListNode(-1);
        ListNode p = head1;
        ListNode node = dummy;
        while (p != null) {
            node.next = new ListNode(p.val * (ch - '0'));
            p = p.next;
            node = node.next;
        }
        // 处理 >10 的字符
        node = dummy.next;
        handleOversizeNodes(node);
        for (int i = 0; i < zeroNums; i++) {
            node = new ListNode(0, node);
        }
        return node;
    }

    void handleOversizeNodes(ListNode head) {
        ListNode p = head, next;
        while (p != null) {
            if (p.val >= 10) {
                next = p.next;
                if (next == null) {
                    p.next = next = new ListNode(0);
                }
                next.val += p.val / 10;
                p.val %= 10;
            }
            p = p.next;
        }
    }

    /**
     * 将多个链表相加
     * 
     */
    ListNode getMultiLinkedListSum(ListNode[] heads) {
        if (heads == null || heads.length < 1) {
            return null;
        }
        if (heads.length == 1) {
            return heads[0];
        }
        ListNode head = heads[0];
        for (int i = 1; i < heads.length; i++) {
            addTwoNumNode(head, heads[i]);
        }
        return head;
    }

    void addTwoNumNode(ListNode head1, ListNode head2) {
        ListNode p1 = head1, p2 = head2;
        ListNode prev = p1;
        while (p1 != null && p2 != null) {
            p1.val += p2.val;
            prev = p1;
            p1 = p1.next;
            p2 = p2.next;
        }
        if (p1 == null && prev != null && p2 != null) {
            prev.next = p2;
        }
        handleOversizeNodes(head1);
    }