一网友在求职的时候，遇到一位hr好心教他改写简历。有网友评论说：他可能是真的饿了。
其实这种情况我之前也遇到过，这些所谓的hr其实都是猎头。简历写的好，面试机会就大，机会大了，成功率就高，面试成功之后他会拿到提成。真正的甲方公司hr一般不会这样让你修改简历的，除非这hr是你老表。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第43题：字符串相乘。
问题描述
来源：LeetCode第43题
难度：中等
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
示例1：
输入: num1 = "123", num2 = "456" 输出: "56088"
1 <= num1.length, num2.length <= 200
num1 和 num2 只能由数字组成。
num1 和 num2 都不包含任何前导零，除了数字0本身。
问题分析
这题让计算两个字符串相乘并且不能使用内置的库函数。如果是单个数字乘以一个字符串，可以使用两个指针一个记录相乘的结果，一个记录进位的值，然后不停的把结果保存下来即可，如下图所示：
如果是多位数字相乘也可以参照单个数字相乘的步骤，每次使用乘数中的其中一位和被乘数相乘。这里的关键点是找出相乘之后应该存放的位置，我们使用一个一维数组来记录。
如下图所示，如果被乘数的第 i 位（从右边数）和乘数的第 j 位（从右边数）相乘，相乘的结果应该放到数组的第 i+j 位（从右边数），注意存放的时候还要加上数组中原来的值，如果结果大于等于10，要取个位数字，然后往前进位。
因为字符串的读取都是从左边开始读取的，而字符串的左边是最高位，最右边才是个位，所以我们要逆序遍历字符串，对于数组的存储我们选择从右边开始存储，因为相乘的结果没有前导0，最后我们把数组转化为字符串的时候可以跳过前面的0。
JAVA：
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();
}C++：
public:
string multiply(string num1, string num2) {
int len1 = num1.size(), len2 = num2.size();
vector
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; }
C：
char *multiply(char *num1, char *num2) {
int len1 = strlen(num1), len2 = strlen(num2);
int total = len1 + len2 + 1;
int *mulArr = malloc(sizeof(int) * total);
memset(mulArr, 0, sizeof(int) * total);
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;// 当前位的值
}
}
// 数组转字符串
char *ans = malloc(sizeof(char) * total);
memset(ans, 0, sizeof(char) * total);
int index = 0;
for (int i = 0; i < len1 + len2; i++) {
// 跳过前面的0
if (index == 0 && mulArr[i] == 0)
continue;
ans[index++] = mulArr[i] + '0';
}
return index == 0 ? "0" : ans;
}Python：
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笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。