精品推荐：
《征服数据结构》专栏：50多种数据结构彻底征服
《经典图论算法》专栏：50多种经典图论算法全部掌握
随着秋招的即将结束，各大厂也在陆续开奖，有的年薪可以达到70万，可以看下前面京东的开奖。而最近小米的开奖引起了部分网友的争议，这年薪，985硕士才22.5万，在各互联网大厂中确实有点垫底了。有网友称：难怪小米每年都招不满，赚那么多钱对应届生那么抠搜。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第43题：字符串相乘。
问题描述
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
输入: num1 = "123", num2 = "456"
输出: "56088"
1 <= num1.length, num2.length <= 200
num1 和 num2 只能由数字组成。
num1 和 num2 都不包含任何前导零，除了数字0本身。
问题分析
如果是多位数字相乘也可以参照单个数字相乘的步骤，每次使用乘数中的其中一位和被乘数相乘。这里的关键点是找出相乘之后应该存放的位置，我们使用一个一维数组来记录。
如下图所示，如果被乘数的第 i 位（从右边数）和乘数的第 j 位（从右边数）相乘，相乘的结果应该放到数组的第 i+j 位（从右边数），注意存放的时候还要加上数组中原来的值，如果结果大于等于10，要取个位数字，然后往前进位。
public String multiply(String num1, String num2) {
int len1 = num1.length(), len2 = num2.length();
int[] mulArr = 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 curIndex = i + j + 1;// 当前数字存放的位置
int carryIndex = curIndex - 1;// 前面进位的位置
int sum = mul + mulArr[curIndex];
mulArr[carryIndex] += sum / 10;// 进位的值
mulArr[curIndex] = sum % 10;// 当前位的值
}
}
// 数组转字符串
StringBuilder sb = new StringBuilder();
for (int num : mulArr) {
// 跳过前面的0
if (sb.length() == 0 && num == 0)
continue;
sb.append(num);
}
return sb.length() == 0 ? "0" : sb.toString();
}
public:
string multiply(string num1, string num2) {
int len1 = num1.size(), len2 = num2.size();
vector<int> mulArr(len1 + len2);
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 curIndex = i + j + 1;// 当前数字存放的位置
int carryIndex = curIndex - 1;// 前面进位的位置
int sum = mul + mulArr[curIndex];
mulArr[carryIndex] += sum / 10;// 进位的值
mulArr[curIndex] = sum % 10;// 当前位的值
}
}
// 数组转字符串
string ans;
for (int num: mulArr) {
// 跳过前面的0
if (ans.empty() && num == 0)
continue;
ans.push_back(num + '0');
}
return ans.empty() ? "0" : ans;
}
def multiply(self, num1: str, num2: str) -> str:
len1, len2 = len(num1), len(num2)
mulArr = [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])
curIndex = i + j + 1 # 当前数字存放的位置
carryIndex = curIndex - 1 # 前面进位的位置
sum = mul + mulArr[curIndex]
mulArr[carryIndex] += sum // 10 # 进位的值
mulArr[curIndex] = sum % 10 # 当前位的值
# 数组转字符串，先过滤掉前面的数字0
index = 0
while mulArr[index] == 0:
index += 1
if index == len(mulArr):
return "0";
ans = "".join(str(x) for x in mulArr[index:])
return ans
