概述
给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积也表示为字符串形式。
输入: num1 = “2”, num2 = “3”
输出: “6”
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/multiply-strings
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
常规思路: 1234 * 456 = 1234 * 6 + 1234 * 50 + 1234 * 400
由于 0 乘以任何数都是 0,所以 1234 * 50 = 1234 * 5 的结果加上一个 0,1234 * 400 的结果等于 1234 * 4 的结果结尾加上两个 0;
其次将计算结果相加,又用到了字符串的加法实现;字符串的加法实现也是类似,从末位开始相加,超过 10 就进位。
实现
class Solution {
public String multiply(String num1, String num2) {
if ("0".equals(num1) || "0".equals(num2)){
return "0";
}
int count = 0; // 表示第几次循环,用于字符串结尾加 0
String answer = "0";
for (int i = num2.length() - 1; i >= 0 ; i--) { // 从 num2 的末尾开始,与 num1 的各个位相乘
char tempNum2 = num2.charAt(i);
int jinwei = 0; // 进位
StringBuilder stringBuilder = new StringBuilder();
int tempNum2Int = tempNum2 - '0';
for (int j = num1.length() - 1; j >= 0 ; j--) { // 将 num1 的各位与 num2 的当前字符相乘
int tempNum1Int = num1.charAt(j) - '0';
int result = tempNum2Int * tempNum1Int + jinwei; //
stringBuilder.append(result % 10);
jinwei = result / 10;
}
if (jinwei > 0){
stringBuilder.append(jinwei);
}
stringBuilder = stringBuilder.reverse();
// 结尾加 0
for (int j = 0; j < count; j++) {
stringBuilder.append("0");
}
count++;
// 大整数加法
answer = stringAdd(answer,stringBuilder.toString());
}
return answer;
}
/**
* 大整数加法
* @param str1
* @param str2
* @return
*/
public String stringAdd(String str1, String str2){
int num1Length = str1.length();
int num2Length = str2.length();
int maxLength = Math.max(num1Length,num2Length);
// 少位的补 0 对齐
if (num1Length < num2Length){
for (int i = 0; i < num2Length-num1Length; i++) {
str1 = '0' + str1;
}
}
if (num1Length > num2Length){
for (int i = 0; i < num1Length-num2Length; i++) {
str2 = '0' + str2;
}
}
StringBuilder stringBuilder = new StringBuilder();
int jinwei = 0;
for (int j = maxLength - 1;j >= 0 ;j--){
int num1 = str1.charAt(j) - '0';
int num2 = str2.charAt(j) - '0';
int ans = num1 + num2 + jinwei;
jinwei = ans / 10;
stringBuilder.append(ans % 10);
}
// 有进位
if (jinwei > 0){
stringBuilder.append(jinwei);
}
return stringBuilder.reverse().toString();
}
}
总结
其实就是考察移位运算的熟练程度,穿插了字符串加法的实现。