力扣00043.字符串相乘

发表于 分类于 阅读次数： 本文字数： 2.3k 阅读时长 ≈ 8 分钟
字符串相乘、数学、字符串、模拟、中等

题目描述

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

示例 1：

输入: num1 = “2”, num2 = “3”
输出: “6”

示例 2：

输入: num1 = “123”, num2 = “456”
输出: “56088”

提示：

  • 1 <= num1.length, num2.length <= 200
  • num1 和 num2 只能由数字组成。
  • num1 和 num2 都不包含任何前导零，除了数字0本身。

解决方法

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    string multiply(string num1, string num2) {
        int len1 = num1.size();
        int len2 = num2.size();
        string result(len1 + len2, '0');
        for (int i = len1 - 1; i >= 0; --i) {
            for (int j = len2 - 1; j >= 0; --j) {
                int mul = (num1[i] - '0') * (num2[j] - '0');
                int sum = mul + (result[i + j + 1] - '0');
                
                result[i + j + 1] = sum % 10 + '0';
                result[i + j] += sum / 10;
            }
        }
        size_t start_pos = result.find_first_not_of('0');
        return (start_pos != string::npos) ? result.substr(start_pos) : "0";
    }
};

结果

执行用时 : 3 ms, 击败 91.44% 使用 C++ 的用户

内存消耗 : 7.98 MB, 击败 51.38% 使用 C++ 的用户

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    public String multiply(String num1, String num2) {
        int len1 = num1.length();
        int len2 = num2.length();
        int[] result = new int[len1 + len2];
        for (int i = len1 - 1; i >= 0; i--) {
            for (int j = len2 - 1; j >= 0; j--) {
                int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                int sum = mul + result[i + j + 1];
                result[i + j + 1] = sum % 10;
                result[i + j] += sum / 10;
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int num : result) {
            sb.append(num);
        }
        int start = 0;
        while (start < sb.length() - 1 && sb.charAt(start) == '0') {
            start++;
        }
        return sb.substring(start);
    }
}

结果

执行用时 : 3 ms, 击败 % 使用 Java 的用户

内存消耗 : 41.18 MB, 击败 % 使用 Java 的用户

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def multiply(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        len1, len2 = len(num1), len(num2)
        result = [0] * (len1 + len2)
        for i in range(len1 - 1, -1, -1):
            for j in range(len2 - 1, -1, -1):
                mul = int(num1[i]) * int(num2[j])
                total_sum = mul + result[i + j + 1]
                result[i + j + 1] = total_sum % 10
                result[i + j] += total_sum // 10
        result_str = ''.join(map(str, result))
        result_str = result_str.lstrip('0')
        return result_str if result_str else '0'

结果

执行用时 : 170 ms, 击败 38.93% 使用 Python 的用户

内存消耗 : 11.59 MB, 击败 86.26% 使用 Python 的用户

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        len1, len2 = len(num1), len(num2)
        result = [0] * (len1 + len2)
        for i in range(len1 - 1, -1, -1):
            for j in range(len2 - 1, -1, -1):
                mul = int(num1[i]) * int(num2[j])
                total_sum = mul + result[i + j + 1]
                result[i + j + 1] = total_sum % 10
                result[i + j] += total_sum // 10
        result_str = ''.join(map(str, result))
        result_str = result_str.lstrip('0')
        return result_str if result_str else '0'

结果

执行用时 : 95 ms, 击败 49.18% 使用 Python3 的用户

内存消耗 : 16.41 MB, 击败 41.37% 使用 Python3 的用户

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
char* multiply(char* num1, char* num2) {
    int len1 = strlen(num1);
    int len2 = strlen(num2);
    int len_result = len1 + len2;
    int* result = (int*)malloc(sizeof(int) * len_result);
    memset(result, 0, sizeof(int) * len_result);
    for (int i = len1 - 1; i >= 0; i--) {
        for (int j = len2 - 1; j >= 0; j--) {
            int mul = (num1[i] - '0') * (num2[j] - '0');
            int sum = mul + result[i + j + 1];
            result[i + j + 1] = sum % 10;
            result[i + j] += sum / 10;
        }
    }
    char* result_str = (char*)malloc(len_result + 1);
    int idx = 0;
    while (idx < len_result && result[idx] == 0) {
        idx++;
    }
    if (idx == len_result) {
        result_str[0] = '0';
        result_str[1] = '\0';
    } else {
        for (int i = idx; i < len_result; i++) {
            result_str[i - idx] = result[i] + '0';
        }
        result_str[len_result - idx] = '\0';
    }
    free(result);
    return result_str;
}

结果

执行用时 : 7 ms, 击败 29.39% 使用 C 的用户

内存消耗 : 6.01 MB, 击败 84.81% 使用 C 的用户

C#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Solution {
    public string Multiply(string num1, string num2) {
        int len1 = num1.Length;
        int len2 = num2.Length;
        int lenResult = len1 + len2;
        int[] result = new int[lenResult];
        for (int i = len1 - 1; i >= 0; i--) {
            for (int j = len2 - 1; j >= 0; j--) {
                int mul = (num1[i] - '0') * (num2[j] - '0');
                int sum = mul + result[i + j + 1];
                result[i + j + 1] = sum % 10;
                result[i + j] += sum / 10;
            }
        }
        StringBuilder resultStr = new StringBuilder();
        int idx = 0;
        while (idx < lenResult && result[idx] == 0) {
            idx++;
        }
        if (idx == lenResult) {
            resultStr.Append('0');
        } else {
            for (int i = idx; i < lenResult; i++) {
                resultStr.Append(result[i]);
            }
        }
        return resultStr.ToString();
    }
}

结果

执行用时 : 63 ms, 击败 79.35% 使用 C# 的用户

内存消耗 : 42.13 MB, 击败 48.91% 使用 C# 的用户

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var multiply = function(num1, num2) {
    const len1 = num1.length;
    const len2 = num2.length;
    const lenResult = len1 + len2;
    const result = Array(lenResult).fill(0);
    for (let i = len1 - 1; i >= 0; i--) {
        for (let j = len2 - 1; j >= 0; j--) {
            const mul = (num1[i] - '0') * (num2[j] - '0');
            const sum = mul + result[i + j + 1];
            result[i + j + 1] = sum % 10;
            result[i + j] += Math.floor(sum / 10);
        }
    }
    let resultStr = '';
    let idx = 0;
    while (idx < lenResult && result[idx] === 0) {
        idx++;
    }
    if (idx === lenResult) {
        resultStr = '0';
    } else {
        for (let i = idx; i < lenResult; i++) {
            resultStr += result[i];
        }
    }
    return resultStr;
};

结果

执行用时 : 70 ms, 击败 69.68% 使用 JavaScript 的用户

内存消耗 : 51.53 MB, 击败 21.49% 使用 JavaScript 的用户

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function multiply(num1: string, num2: string): string {
    const len1 = num1.length;
    const len2 = num2.length;
    const lenResult = len1 + len2;
    const result: number[] = Array(lenResult).fill(0);
    for (let i = len1 - 1; i >= 0; i--) {
        for (let j = len2 - 1; j >= 0; j--) {
            const mul = (num1[i].charCodeAt(0) - '0'.charCodeAt(0)) * (num2[j].charCodeAt(0) - '0'.charCodeAt(0));
            const sum = mul + result[i + j + 1];
            result[i + j + 1] = sum % 10;
            result[i + j] += Math.floor(sum / 10);
        }
    }
    let resultStr = '';
    let idx = 0;
    while (idx < lenResult && result[idx] === 0) {
        idx++;
    }
    if (idx === lenResult) {
        resultStr = '0';
    } else {
        for (let i = idx; i < lenResult; i++) {
            resultStr += result[i];
        }
    }
    return resultStr;
}

结果

执行用时 : 67 ms, 击败 90.00% 使用 TypeScript 的用户

内存消耗 : 52.91 MB, 击败 15.71% 使用 TypeScript 的用户

PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    
    /**
     * @param String $num1
     * @param String $num2
     * @return String
     */
    function multiply($num1, $num2) {
        $len1 = strlen($num1);
        $len2 = strlen($num2);
        $lenResult = $len1 + $len2;
        $result = array_fill(0, $lenResult, 0);
        for ($i = $len1 - 1; $i >= 0; $i--) {
            for ($j = $len2 - 1; $j >= 0; $j--) {
                $mul = intval($num1[$i]) * intval($num2[$j]);
                $sum = $mul + $result[$i + $j + 1];
                $result[$i + $j + 1] = $sum % 10;
                $result[$i + $j] += intdiv($sum, 10);
            }
        }
        $resultStr = '';
        $idx = 0;
        while ($idx < $lenResult && $result[$idx] === 0) {
            $idx++;
        }
        if ($idx === $lenResult) {
            $resultStr = '0';
        } else {
            for ($i = $idx; $i < $lenResult; $i++) {
                $resultStr .= $result[$i];
            }
        }
        return $resultStr;
    }
}

结果

执行用时 : 32 ms, 击败 0.00% 使用 PHP 的用户

内存消耗 : 19.91 MB, 击败 0.00% 使用 PHP 的用户

Swift

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    func multiply(_ num1: String, _ num2: String) -> String {
        let len1 = num1.count
        let len2 = num2.count
        let lenResult = len1 + len2
        var result = Array(repeating: 0, count: lenResult)
        for i in stride(from: len1 - 1, through: 0, by: -1) {
            for j in stride(from: len2 - 1, through: 0, by: -1) {
                let mul = Int(String(num1[num1.index(num1.startIndex, offsetBy: i)]))! * Int(String(num2[num2.index(num2.startIndex, offsetBy: j)]))!
                let sum = mul + result[i + j + 1]
                result[i + j + 1] = sum % 10
                result[i + j] += sum / 10
            }
        }
        var resultStr = ""
        var idx = 0
        while idx < lenResult && result[idx] == 0 {
            idx += 1
        }
        if idx == lenResult {
            resultStr = "0"
        } else {
            for i in idx..<lenResult {
                resultStr += String(result[i])
            }
        }
        return resultStr
    }
}

结果

执行用时 : 195 ms, 击败 7.32% 使用 Swift 的用户

内存消耗 : 16.23 MB, 击败 7.32% 使用 Swift 的用户

Kotlin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    fun multiply(num1: String, num2: String): String {
        val len1 = num1.length
        val len2 = num2.length
        val lenResult = len1 + len2
        val result = IntArray(lenResult)
        for (i in len1 - 1 downTo 0) {
            for (j in len2 - 1 downTo 0) {
                val mul = (num1[i] - '0') * (num2[j] - '0')
                val sum = mul + result[i + j + 1]
                result[i + j + 1] = sum % 10
                result[i + j] += sum / 10
            }
        }
        val resultStr = StringBuilder()
        var idx = 0
        while (idx < lenResult && result[idx] == 0) {
            idx++
        }
        if (idx == lenResult) {
            resultStr.append('0')
        } else {
            for (i in idx until lenResult) {
                resultStr.append(result[i])
            }
        }
        return resultStr.toString()
    }
}

结果

执行用时 : 176 ms, 击败 100.00% 使用 Kotlin 的用户

内存消耗 : 35.16 MB, 击败 81.82% 使用 Kotlin 的用户

Dart

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
  String multiply(String num1, String num2) {
    int len1 = num1.length;
    int len2 = num2.length;
    int lenResult = len1 + len2;
    List<int> result = List.filled(lenResult, 0);
    for (int i = len1 - 1; i >= 0; i--) {
      for (int j = len2 - 1; j >= 0; j--) {
        int mul = int.parse(num1[i]) * int.parse(num2[j]);
        int sum = mul + result[i + j + 1];
        result[i + j + 1] = sum % 10;
        result[i + j] += sum ~/ 10;
      }
    }
    StringBuffer resultStr = StringBuffer();
    int idx = 0;
    while (idx < lenResult && result[idx] == 0) {
      idx++;
    }
    if (idx == lenResult) {
      resultStr.write('0');
    } else {
      for (int i = idx; i < lenResult; i++) {
        resultStr.write(result[i]);
      }
    }
    return resultStr.toString();
  }
}

结果

执行用时 : 317 ms, 击败 -% 使用 Dart 的用户

内存消耗 : 143.64 MB, 击败 100.00% 使用 Dart 的用户

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func multiply(num1 string, num2 string) string {
    len1, len2 := len(num1), len(num2)
    lenResult := len1 + len2
    result := make([]int, lenResult)
    for i := len1 - 1; i >= 0; i-- {
        for j := len2 - 1; j >= 0; j-- {
            mul := int(num1[i]-'0') * int(num2[j]-'0')
            sum := mul + result[i+j+1]
            result[i+j+1] = sum % 10
            result[i+j] += sum / 10
        }
    }
    var resultStr string
    idx := 0
    for idx < lenResult && result[idx] == 0 {
        idx++
    }
    if idx == lenResult {
        resultStr = "0"
    } else {
        for i := idx; i < lenResult; i++ {
            resultStr += strconv.Itoa(result[i])
        }
    }
    return resultStr
}

结果

执行用时 : 3 ms, 击败 60.96% 使用 Go 的用户

内存消耗 : 2.93 MB, 击败 64.82% 使用 Go 的用户

Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# @param {String} num1
# @param {String} num2
# @return {String}
def multiply(num1, num2)
    len1, len2 = num1.length, num2.length
    len_result = len1 + len2
    result = Array.new(len_result, 0)
    (len1 - 1).downto(0) do |i|
        (len2 - 1).downto(0) do |j|
            mul = num1[i].to_i * num2[j].to_i
            sum = mul + result[i + j + 1]
            result[i + j + 1] = sum % 10
            result[i + j] += sum / 10
        end
    end
    idx = 0
    while idx < len_result && result[idx] == 0
        idx += 1
    end
    if idx == len_result
        result_str = '0'
    else
        result_str = result[idx..-1].join
    end
    result_str
end

结果

执行用时 : 145 ms, 击败 100.00% 使用 Ruby 的用户

内存消耗 : 206.50 MB, 击败 -% 使用 Ruby 的用户

Scala

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
object Solution {
  def multiply(num1: String, num2: String): String = {
    val len1 = num1.length
    val len2 = num2.length
    val lenResult = len1 + len2
    val result = Array.fill(lenResult)(0)
    for (i <- len1 - 1 to 0 by -1) {
      for (j <- len2 - 1 to 0 by -1) {
        val mul = (num1(i) - '0') * (num2(j) - '0')
        val sum = mul + result(i + j + 1)
        result(i + j + 1) = sum % 10
        result(i + j) += sum / 10
      }
    }
    val idx = result.indexWhere(_ != 0)
    val resultStr =
      if (idx == -1) "0"
      else result.slice(idx, lenResult).mkString
    resultStr
  }
}

结果

执行用时 : 504 ms, 击败 100.00% 使用 Scala 的用户

内存消耗 : 54.61 MB, 击败 100.00% 使用 Scala 的用户

Rust

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
impl Solution {
    pub fn multiply(num1: String, num2: String) -> String {
        let len1 = num1.len();
        let len2 = num2.len();
        let len_result = len1 + len2;
        let mut result = vec![0; len_result];
        for (i, c1) in num1.chars().rev().enumerate() {
            for (j, c2) in num2.chars().rev().enumerate() {
                let mul = (c1.to_digit(10).unwrap()) * (c2.to_digit(10).unwrap());
                let sum = mul + result[i + j];
                result[i + j] = sum % 10;
                result[i + j + 1] += sum / 10;
            }
        }
        let mut result_str: String = result
            .iter()
            .rev()
            .skip_while(|&&x| x == 0)
            .map(|&x| char::from_digit(x, 10).unwrap())
            .collect();
        if result_str.is_empty() {
            result_str.push('0');
        }
        result_str
    }
}

结果

执行用时 : 2 ms, 击败 33.33% 使用 Rust 的用户

内存消耗 : 2.14 MB, 击败 55.56% 使用 Rust 的用户

Racket

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Racket 的用户

内存消耗 : MB, 击败 % 使用 Racket 的用户

Erlang

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Erlang 的用户

内存消耗 : MB, 击败 % 使用 Erlang 的用户

Elixir

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Elixir 的用户

内存消耗 : MB, 击败 % 使用 Elixir 的用户