字符串相乘
难度:
标签:
题目描述
给定两个以字符串形式表示的非负整数 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本身。
代码结果
运行时间: 144 ms, 内存: 15.1 MB
/*
* 思路：
* 1. 我们可以使用IntStream来遍历两个字符串的每一位，从右往左逐位相乘。
* 2. 使用平铺的lambda表达式来模拟双重循环和乘法的累加。
* 3. 最终将结果数组中的每个元素转换为字符，合并成最终结果。
*/
import java.util.stream.IntStream;
public class Solution {
public String multiply(String num1, String num2) {
int m = num1.length(), n = num2.length();
int[] result = new int[m + n];
IntStream.range(0, m).forEach(i -> {
IntStream.range(0, n).forEach(j -> {
int mul = (num1.charAt(m - 1 - i) - '0') * (num2.charAt(n - 1 - j) - '0');
int sum = mul + result[i + j];
result[i + j] = sum % 10;
result[i + j + 1] += sum / 10;
});
});
StringBuilder sb = new StringBuilder();
IntStream.range(0, result.length)
.map(i -> result[result.length - 1 - i])
.dropWhile(i -> i == 0)
.forEach(sb::append);
return sb.length() == 0 ? "0" : sb.toString();
}
}解释
方法:
这个题解使用了模拟竖式乘法的方法来计算两个字符串表示的数字相乘的结果。具体做法是：
1. 如果其中一个数字是0，直接返回'0'。
2. 创建一个长度为 m+n 的数组 ans 用于存储计算结果的每一位。
3. 从右往左遍历 num1 和 num2 的每个数字，将对应位置的数字相乘，再加上 ans 数组中对应位置的值。
4. 将乘积的个位数存入 ans 数组的 p2 位置，将十位数加到 p1 位置。
5. 遍历完成后，将 ans 数组转换为字符串，并去除前导0（如果有）。
时间复杂度:
O(m*n)
空间复杂度:
O(m+n)
代码细节讲解
🦆
为什么在遍历num1和num2的时候选择从右向左遍历，而不是从左向右？
▷🦆
在计算每一位的乘积后，为什么需要即时加上数组ans中对应位置的值？这种累加的处理对结果的正确性有什么影响？
▷🦆
你如何处理乘积结果数组ans中的进位？具体是如何确定进位的十位数和个位数分别添加到哪个位置的？
▷🦆
在去除前导零的过程中，如果所有位都是零（即结果为0），这种情况是如何处理的？
▷相关问题
两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[7,0,8] 解释：342 + 465 = 807.
示例 2：
输入：l1 = [0], l2 = [0] 输出：[0]
示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 输出：[8,9,9,9,0,0,0,1]
提示：
- 每个链表中的节点数在范围
[1, 100]内 0 <= Node.val <= 9- 题目数据保证列表表示的数字不含前导零
加一
给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
示例 1：
输入：digits = [1,2,3] 输出：[1,2,4] 解释：输入数组表示数字 123。
示例 2：
输入：digits = [4,3,2,1] 输出：[4,3,2,2] 解释：输入数组表示数字 4321。
示例 3：
输入：digits = [0] 输出：[1]
提示：
1 <= digits.length <= 1000 <= digits[i] <= 9
二进制求和
给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。
示例 1：
输入:a = "11", b = "1" 输出："100"
示例 2：
输入：a = "1010", b = "1011" 输出："10101"
提示：
1 <= a.length, b.length <= 104a和b仅由字符'0'或'1'组成- 字符串如果不是
"0"，就不含前导零
字符串相加
给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。
你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。
示例 1：
输入：num1 = "11", num2 = "123" 输出："134"
示例 2：
输入：num1 = "456", num2 = "77" 输出："533"
示例 3：
输入：num1 = "0", num2 = "0" 输出："0"
提示：
1 <= num1.length, num2.length <= 104num1和num2都只包含数字0-9num1和num2都不包含任何前导零