快手 LeetCode 43.字符串相乘

思路乘法的竖式运算。1.注意1如果乘数num1的位数为m乘数num2的位数为n那么num1 × num2的结果res的最大总位数为m n。2对于num1[i]×num2[j]其结果一定为1-2位且第一位前一位位于res[i j]第二位后一位位于res[i j 1]。结合下图更容易理解2.复杂度分析1时间复杂度O(m * n)其中m和n分别为两个字符串的长度。2空间复杂度O(m n)存储结果数组。附代码class Solution { public String multiply(String num1, String num2) { if(num1.equals(0) || num2.equals(0)){ return 0; } int[] calcu new int[num1.length() num2.length()]; for(int i num1.length() - 1;i 0;i--){ int n1 num1.charAt(i) - 0; for(int j num2.length() - 1;j 0;j--){ int n2 num2.charAt(j) - 0; // res[i j 1]表示该位置原来已有的值可能有原来的进位 // n1 * n2表示当前两位数字的乘积 int sum (calcu[i j 1] n1 * n2); // 表示当前位应该放的放的数字 calcu[i j 1] sum % 10; // 累加进位加到前一个位置i j calcu[i j] sum / 10; } } StringBuilder res new StringBuilder(); for(int i 0;i calcu.length;i){ // 跳过前导0 // 两个非0数字相乘最多只有一个前导0 if(i 0 calcu[i] 0){ continue; } res.append(calcu[i]); } return res.toString(); } }ACM模式import java.util.Scanner; class Solution { public String multiply(String num1, String num2) { if (num1.equals(0) || num2.equals(0)) { return 0; } int[] calcu new int[num1.length() num2.length()]; for (int i num1.length() - 1; i 0; i--) { int n1 num1.charAt(i) - 0; for (int j num2.length() - 1; j 0; j--) { int n2 num2.charAt(j) - 0; int sum calcu[i j 1] n1 * n2; calcu[i j 1] sum % 10; calcu[i j] sum / 10; } } StringBuilder res new StringBuilder(); for (int i 0; i calcu.length; i) { if (i 0 calcu[i] 0) { continue; } res.append(calcu[i]); } return res.toString(); } } public class Main { public static void main(String[] args) { Scanner scanner new Scanner(System.in); // 读取两个数字字符串 // 支持两个字符串之间用空格分隔无需换行 String num1 scanner.next(); String num2 scanner.next(); // 计算乘积 Solution solution new Solution(); String result solution.multiply(num1, num2); System.out.println(result); scanner.close(); } }