[LeetCode 43]Multiply Strings

题目链接：multiply-strings

import java.util.Arrays;/** * Given two numbers represented as strings, return multiplication of the numbers as a string.Note: The numbers can be arbitrarily large and are non-negative. * */public class MultiplyStrings {//解法一//311 / 311 test cases passed.//Status: Accepted//Runtime: 232 ms//Submitted: 0 minutes agostatic String multiply(String num1, String num2) {String multi = "";int[] nums = new int[num1.length() + num2.length()];Arrays.fill(nums, 0);for(int i = num1.length() – 1; i >= 0; i –) {for(int j = num2.length() – 1; j >= 0; j –) {nums[i + j + 1] += (num1.charAt(i) – '0') * (num2.charAt(j) – '0');}}for (int i = nums.length – 1; i >= 1; i–) {nums[i – 1] += nums[i] / 10;nums[i] %= 10;}int begin = 0;while(begin < nums.length – 1 && nums[begin] == 0) begin ++;for (int i = begin; i <= nums.length – 1; i ++) {multi += nums[i];}return multi;}//解法二//311 / 311 test cases passed.//Status: Accepted//Runtime: 394 ms//Submitted: 0 minutes ago//代码略显臃肿，有待优化static String multiply1(String num1, String num2) {String multi = "";String temp = num2;for(int i = num1.length() – 1; i >= 0; i –) {int n = num1.charAt(i) – '0';multi = add(multi, multiply(temp, n));temp += "0";}int begin = 0;while(begin < multi.length() – 1 && multi.charAt(begin) == '0') begin ++;return multi.substring(begin);}static String multiply(String num1, int num2) {String multi = "";if(num2 == 0) return "0";int carray = 0;for(int i = num1.length() – 1; i >= 0; i –) {int n = (num1.charAt(i) – '0') * num2 + carray;multi = n % 10 + multi;carray = n / 10;}if(carray != 0) {multi = carray % 10 + multi;}return multi;}static String add(String a, String b) {String sum = "";int carray = 0;if(a.length() > b.length()) {String temp = a;a = b;b = temp;}//使a和b的长度相等int gap = b.length() – a.length();while((gap–) != 0) a = "0" + a;for (int i = b.length() – 1; i >= 0; i–) {int n = a.charAt(i) – '0' + b.charAt(i) – '0' + carray;sum = (n % 10) + sum;carray = n / 10;}if(carray != 0) sum = carray % 10 + sum;return sum;}public static void main(String[] args) {System.out.println(multiply("1000000", "99999"));System.out.println(multiply("1000000000000000000000000000000000000000000", "1000000000000000000000000000000000000000000"));}}

，天不负;卧薪尝胆，三千越甲可吞吴。