LeetCode-043-字符串相乘 LeetCode-043-字符串相乘

字符串相乘

题目描述：给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
示例说明请见LeetCode官网。
【LeetCode-043-字符串相乘】来源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一：数组遍历

首先，如果num1和num2有为0的，直接返回空字符串。

否则，声明一个list为temp用来记录每一行的乘积的结果；

然后将这些行的结果累加起来；

最后将累加的结果按倒序拼成字符串返回。

import java.util.ArrayList; import java.util.List; public class LeetCode_043 { public static String multiply(String num1, String num2) { if ((num1 == null || num1.length() == 0) || (num2 == null || num2.length() == 0)) { return ""; } if (num1.equals("0") || num2.equals("0")) { return "0"; } /** * 如果num2的长度大于num1的长度将num1和num2的值交换 */ if (num2.length() > num1.length()) { String temp = num1; num1 = num2; num2 = temp; } /** * 记录每一行的乘积的结果 */ List temp = new ArrayList<>(); int count = 0; for (int i = num2.length() - 1; i >= 0; i--) { int c2Num = num2.charAt(i) - '0'; int[] cur = new int[num1.length() + num2.length()]; int index = 0; for (; index < count; index++) { cur[index] = 0; } int addOne = 0; for (int j = num1.length() - 1; j >= 0; j--) { int c1Num = num1.charAt(j) - '0'; if (c2Num * c1Num + addOne > 9) { cur[index++] = (c2Num * c1Num + addOne) % 10; addOne = (c2Num * c1Num + addOne) / 10; } else { cur[index++] = c2Num * c1Num + addOne; addOne = 0; } } if (addOne > 0) { cur[index] = addOne; } temp.add(cur); count++; }int addOne = 0; List result = new ArrayList<>(); /** * 将每一行的乘积结果累加起来 */ for (int i = 0; i < num1.length() + num2.length(); i++) { int curNum = addOne; for (int[] ints : temp) { curNum += ints[i]; } if (curNum > 9) { result.add(curNum % 10); addOne = curNum / 10; } else { result.add(curNum % 10); addOne = 0; } }String resultStr = ""; int firstNoneZeroIndex = -1; /** * 找到第一个不为0的数字 */ for (int i = result.size() - 1; i >= 0; i--) { if (result.get(i) != 0) { firstNoneZeroIndex = i; break; } } /** * 将最后的结果拼成string并最后返回 */ for (int i = firstNoneZeroIndex; i >= 0; i--) { resultStr += String.valueOf(result.get(i)); } return resultStr; }public static void main(String[] args) { // 测试用例，预计输出： 56088 System.out.println(multiply("123", "456")); } }