Bài 43 Leetcode: Multiply Strings

Đề bài:

Cho hai số nguyên không âm num1 và num2 được biểu diễn dưới dạng chuỗi, trả về tích của num1 và num2, cũng được biểu diễn dưới dạng chuỗi.

Chú ý: Bạn không được sử dụng bất kỳ thư viện BigInteger tích hợp sẵn nào hoặc chuyển đổi đầu vào thành số nguyên trực tiếp.

Ví dụ 1:

Input: num1 = "2", num2 = "3"
Output: "6"

Ví dụ 2:

Input: num1 = "123", num2 = "456"
Output: "56088"

Ràng buộc:

  • 1 <= độ dài của chuỗi num1, num2 <= 200
  • num1 và num2 chỉ chứa các chữ số.
  • Cả num1 và num2 không chứa bất kỳ số 0 dẫn đầu nào, trừ số 0 chính nó.

Giải thích thuật toán bằng C ++

class Solution {
 public:
  string multiply(string num1, string num2) {
    string s(num1.length() + num2.length(), '0');

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

    const int i = s.find_first_not_of('0');
    return i == -1 ? "0" : s.substr(i);
  }
};

Đoạn mã trên là một đoạn mã C++ để tính tích của hai số nguyên dương `num1` và `num2`, được biểu diễn dưới dạng chuỗi. Dưới đây là giải thích về thuật toán trong đoạn mã:

1. Hàm `multiply` nhận hai chuỗi `num1` và `num2` là các số nguyên dương và trả về tích của chúng dưới dạng chuỗi.

2. Đầu tiên, ta khởi tạo một chuỗi `s` có độ dài bằng tổng độ dài của `num1` và `num2`, và tất cả các ký tự trong chuỗi đều là ‘0’. Chuỗi `s` sẽ được sử dụng để lưu trữ kết quả cuối cùng.

3. Sử dụng hai vòng lặp lồng nhau, ta đi qua từng chữ số của `num1` và `num2` từ cuối chuỗi về đầu. Trong quá trình này, ta thực hiện các phép nhân số học giữa hai chữ số tương ứng và tính tổng của tích đó với giá trị hiện tại của chuỗi `s`.

4. Đối với mỗi cặp chữ số, ta tính tích của chúng bằng cách lấy hiệu số giữa mã ASCII của chữ số đó và mã ASCII của ký tự ‘0’. Sau đó, ta cộng tích đó với giá trị tại vị trí tương ứng trong chuỗi `s`. Điều này sẽ tính toán tổng của tích và giá trị hiện tại của chuỗi `s`.

5. Trong quá trình tính toán tổng, ta cần xử lý trường hợp khi tổng vượt qua 9 (tức là có một phần tử có giá trị lớn hơn 9). Ta cập nhật vị trí trước đó trong chuỗi `s` bằng cách thêm phần nguyên của tổng chia cho 10, và cập nhật vị trí hiện tại bằng phần dư của tổng chia cho 10Để hiểu rõ hơn, ta có thể xem qua một ví dụ:

Giả sử num1 = “123” và num2 = “45”.

– Lần lặp đầu tiên:

+ mult = (3 – ‘0’) * (5 – ‘0’) = 3 * 5 = 15
+ sum = 15 + (s[3] – ‘0’) = 15 + 0 = 15
+ s[2] += 15 / 10 = ‘0’ + 1 = ‘1’
+ s[3] = ‘0’ + 15 % 10 = ‘0’ + 5 = ‘5’
+ Chuỗi s sau vòng lặp đầu tiên: “005”

– Lần lặp thứ hai:

+ mult = (2 – ‘0’) * (5 – ‘0’) = 2 * 5 = 10
+ sum = 10 + (s[2] – ‘0’) = 10 + 0 = 10
+ s[1] += 10 / 10 = ‘0’ + 1 = ‘1’
+ s[2] = ‘0’ + 10 % 10 = ‘0’ + 0 = ‘0’
+ Chuỗi s sau vòng lặp thứ hai: “010”

– Lần lặp thứ ba:

+ mult = (1 – ‘0’) * (5 – ‘0’) = 1 * 5 = 5
+ sum = 5 + (s[1] – ‘0’) = 5 + 1 = 6
+ s[0] += 6 / 10 = ‘0’ + 0 = ‘0’
+ s[1] = ‘0’ + 6 % 10 = ‘0’ + 6 = ‘6’
+ Chuỗi s sau vòng lặp thứ ba: “006”

Cuối cùng, ta tìm vị trí đầu tiên không phải là ‘0’ trong chuỗi s bằng cách sử dụng hàm `find_first_not_of(‘0’)`. Nếu không tìm thấy, ta trả về chuỗi “0”, ngược lại ta trả về một phần của chuỗi s từ vị trí đầu tiên không phải là ‘0’ đến cuối chuỗi.

Với ví dụ trên, chuỗi s sau cùng là “006” và vị trí đầu tiên không phải là ‘0’ là 0. Do đó, kết quả cuối cùng là “006”.

Giải thích thuật toán bằng Java

class Solution {
  public String multiply(String num1, String num2) {
    final int m = num1.length();
    final int n = num2.length();

    StringBuilder sb = new StringBuilder();
    int[] pos = new int[m + n];

    for (int i = m - 1; i >= 0; --i)
      for (int j = n - 1; j >= 0; --j) {
        final int multiply = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
        final int sum = multiply + pos[i + j + 1];
        pos[i + j] += sum / 10;
        pos[i + j + 1] = sum % 10;
      }

    for (final int p : pos)
      if (p > 0 || sb.length() > 0)
        sb.append(p);

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

Giải thích thuật toán bằng Python

class Solution:
  def multiply(self, num1: str, num2: str) -> str:
    s = [0] * (len(num1) + len(num2))

    for i in reversed(range(len(num1))):
      for j in reversed(range(len(num2))):
        mult = int(num1[i]) * int(num2[j])
        summ = mult + s[i + j + 1]
        s[i + j] += summ // 10
        s[i + j + 1] = summ % 10

    for i, c in enumerate(s):
      if c != 0:
        break

    return ''.join(map(str, s[i:]))

 

Leave a Reply

Your email address will not be published. Required fields are marked *

PHP Code Snippets Powered By : XYZScripts.com
.
.
.
.