问题描述
LeetCode 43. 字符串相乘 (opens in a new tab)，难度中等。
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
**注意：**不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
示例 1
输入: num1 = "2", num2 = "3" 输出: "6"
示例 2
输入: num1 = "123", num2 = "456" 输出: "56088"
提示：
1 <= num1.length, num2.length <= 200num1和num2只能由数字组成。num1和num2都不包含任何前导零，除了数字0本身。
题解
Solution.java
class Solution {
// 大数相加
public String add(String num1, String num2) {
// 字符串反转
num1 = new StringBuffer(num1).reverse().toString();
num2 = new StringBuffer(num2).reverse().toString();
StringBuilder result = new StringBuilder();
int i = 0;
int plus = 0;
while (i < num1.length() || i < num2.length()) {
int n1 = i < num1.length() ? Integer.parseInt(String.valueOf(num1.charAt(i))) : 0;
int n2 = i < num2.length() ? Integer.parseInt(String.valueOf(num2.charAt(i))) : 0;
result.append((n1 + n2 + plus) % 10);
// 进位
plus = (n1 + n2 + plus) / 10;
i++;
}
// 处理高位进位
if (plus != 0) {
result.append(plus);
}
return result.reverse().toString();
}
public String multiply(String num1, String num2) {
String result = "0";
if ("0".equals(num1) || "0".equals(num2)) return "0";
num1 = new StringBuffer(num1).reverse().toString();
num2 = new StringBuffer(num2).reverse().toString();
// num2 每位乘 num1
for (int i = 0; i < num2.length(); ++i) {
StringBuilder temp = new StringBuilder();
int plus = 0;
int currN = Integer.parseInt(String.valueOf(num2.charAt(i)));
for (int j = 0; j < num1.length(); ++j) {
int n = Integer.parseInt(String.valueOf(num1.charAt(j)));
temp.append((currN * n + plus) % 10);
plus = (currN * n + plus) / 10;
}
if (plus != 0) {
temp.append(plus);
}
temp.reverse();
// 高位乘 10 的倍数
int k = i;
while (k-- > 0) {
temp.append("0");
}
result = add(result, temp.toString());
}
return result;
}
}