字符串乘法计算
Info
已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~
读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
| LeetCode | Difficulty |
|---|---|
| 43. Multiply Strings | 🟠 |
For small numbers, you can directly use the operators provided by programming languages for calculations. However, if the two factors to be multiplied are very large, the data types provided by the language may overflow. One alternative is to input the operands as strings and then mimic the multiplication process we learned in elementary school to calculate the result, also represented as a string.
Take a look at LeetCode problem #43 "Multiply Strings":
43. Multiply Strings | 力扣 | LeetCode |
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.
Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.
Example 1:
Input: num1 = "2", num2 = "3" Output: "6"
Example 2:
Input: num1 = "123", num2 = "456" Output: "56088"
Constraints:
1 <= num1.length, num2.length <= 200num1andnum2consist of digits only.- Both
num1andnum2do not contain any leading zero, except the number0itself.
Note that num1 and num2 can be very long, so you cannot simply convert them to integers and perform the operation. The only approach is to mimic manual multiplication.
For example, if we manually calculate 123 × 45, we would do it like this:
Calculate 123 × 5, then 123 × 4, and finally add them with proper alignment. This process is something even elementary students can do proficiently. But can you further mechanize this process and write a set of algorithmic instructions for a computer to execute, which has no intelligence?
This simple process involves multiplication carry-over, misaligned addition, and addition carry-over. There are also subtle issues, such as when multiplying two-digit numbers, the result could be a four-digit number or a three-digit number. How do you come up with a standardized way to handle this? This is the charm of algorithms. Without computational thinking, even simple problems might not be automated.
First, our manual method is still too "advanced". We need to be more "primitive". The processes of 123 × 5 and 123 × 4 can be further broken down before adding them together:
Now, 123 is not large, but if it were a very large number, we couldn't directly calculate the product. We can use an array to accumulate the addition results:
The entire calculation process is roughly like this: two pointers i and j traverse num1 and num2, calculating the product and adding it to the correct position in res, as shown in the GIF below:
Now, there is a key question: how do we add the product to the correct position in res, or how do we calculate the corresponding index in res using i and j?
Actually, with careful observation, you'll notice that the product of num1[i] and num2[j] corresponds to the positions res[i+j] and res[i+j+1].
Understanding this, you can write code to mimic this calculation process:
class Solution {
public String multiply(String num1, String num2) {
int m = num1.length(), n = num2.length();
// the result can be at most m + n digits
int[] res = new int[m + n];
// start multiplying from the least significant digit
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
// the product is at the corresponding index in res
int p1 = i + j, p2 = i + j + 1;
// add to res
int sum = mul + res[p2];
res[p2] = sum % 10;
res[p1] += sum / 10;
}
}
// the leading zeros that might exist in the result (unused digits)
int i = 0;
while (i < res.length && res[i] == 0)
i++;
// convert the calculation result to a string
StringBuilder str = new StringBuilder();
for (; i < res.length; i++)
str.append(res[i]);
return str.length() == 0 ? "0" : str.toString();
}
}class Solution {
public:
string multiply(string num1, string num2) {
int m = num1.size(), n = num2.size();
// the result can have at most m + n digits
vector<int> res(m + n);
// start multiplying from the least significant digit
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
int mul = (num1[i] - '0') * (num2[j] - '0');
// the product is at the corresponding index in res
int p1 = i + j, p2 = i + j + 1;
// add to res
int sum = mul + res[p2];
res[p2] = sum % 10;
res[p1] += sum / 10;
}
}
// there may be leading zeros in the result (unused digits)
int i = 0;
while (i < res.size() && res[i] == 0)
i++;
// convert the calculation result to a string
string str;
for (; i < res.size(); i++)
str.push_back(res[i]+'0');
return str.empty() ? "0" : str;
}
};class Solution:
def multiply(self, num1, num2):
m, n = len(num1), len(num2)
# the result can have at most m + n digits
res = [0] * (m + n)
# start multiplying from the least significant digit
for i in reversed(range(m)):
for j in reversed(range(n)):
mul = (ord(num1[i]) - ord('0')) * (ord(num2[j]) - ord('0'))
# the product is at the corresponding index in res
p1, p2 = i + j, i + j + 1
# add to res
summ = mul + res[p2]
res[p2] = summ % 10
res[p1] += summ // 10
# there may be leading zeros in the result (unused digits)
i = 0
while i < len(res) and res[i] == 0:
i += 1
# convert the calculation result to a string
str_res = ''.join(str(x) for x in res[i:])
return "0" if not str_res else str_resfunc multiply(num1 string, num2 string) string {
m, n := len(num1), len(num2)
// the result can have at most m + n digits
res := make([]int, m + n)
// start multiplying from the least significant digit
for i := m - 1; i >= 0; i-- {
for j := n - 1; j >= 0; j-- {
mul := int(num1[i] - '0') * int(num2[j] - '0')
// the product is at the corresponding index in res
p1, p2 := i + j, i + j + 1
// add to res
sum := mul + res[p2]
res[p2] = sum % 10
res[p1] += sum / 10
}
}
// possible leading zeros in the result (unused digits)
i := 0
for i < len(res) && res[i] == 0 {
i++
}
// convert the calculation result to a string
var str strings.Builder
for ; i < len(res); i++ {
str.WriteString(strconv.Itoa(res[i]))
}
if str.String() == "" {
return "0"
}
return str.String()
}var multiply = function(num1, num2) {
let m = num1.length, n = num2.length;
// the result can have at most m + n digits
let res = new Array(m + n).fill(0);
// start multiplying from the least significant digit
for (let i = m - 1; i >= 0; i--) {
for (let j = n - 1; j >= 0; j--) {
let mul = (num1[i] - '0') * (num2[j] - '0');
// the product is at the corresponding index in res
let p1 = i + j, p2 = i + j + 1;
// add to res
let sum = mul + res[p2];
res[p2] = sum % 10;
res[p1] += Math.floor(sum / 10);
}
}
// the leading zeros in the result (unused digits)
let i = 0;
while (i < res.length && res[i] == 0)
i++;
// convert the calculation result to a string
let str = "";
for (; i < res.length; i++)
str += res[i];
return str.length == 0 ? "0" : str;
}Here, we have completed the string multiplication algorithm.
To summarize, some of the ways of thinking that we take for granted are actually very difficult for computers to achieve. For example, our usual arithmetic process is not complicated, but translating it into code logic is not simple. Algorithms need to simplify the calculation process, obtaining results through a method of calculating and accumulating simultaneously.
Proverbs teach us not to fall into fixed patterns of thinking, to avoid being procedural, and to think creatively. However, I believe that being procedural is not necessarily a bad thing; it can greatly improve efficiency and reduce the rate of errors. Isn't an algorithm a set of procedural thinking? Only through procedural methods can we enable computers to help us solve complex problems!
Perhaps algorithms are a kind of thinking that seeks fixed patterns of thought. I hope this article has been helpful to you.
