首页 > 代码库 > [leetcode]multiply-strings java代码
[leetcode]multiply-strings java代码
题目:
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.
给两个用字符串表示的数字，求它们的乘积。
注意：数字非负，且可以无限大
————————————————————————
之前未考虑数字可以无限大的情况，采用的方法是 将字符串转化为数字，然后相乘，将乘积再次转化为字符串 输出，
最后发现只能通过一部分的测试用例，对于超过long类型表示范围的数字，无法通过。
-----------------------------------------------------
方法思想：根据乘法的演算过程
------------------------------------------
代码：（在牛客网上可以ac，但是leetcode有个用例过不去，超时问题）
public class Solution { public String multiply(String num1, String num2){ if(num1.equals("0")|| num2.equals("0")) return "0"; if(num1.charAt(0) == ‘-‘ || num2.charAt(0) == ‘-‘) return "false"; int len_num1,len_num2; len_num1 = num1.length(); len_num2 = num2.length(); String [] sing_mul = new String[len_num2]; int maxLen_sing = 0; for(int z=0; z<len_num2; z++) //初始化 sing_mul[z] = ""; int times = 0; //被乘数*乘数 --> 返回是字符串数组sing_mul，每一个元素是某个乘数位*被乘数的结果。 for(int i=len_num2-1; i>=0; i--){ int num2Cur = Integer.parseInt(String.valueOf(num2.charAt(i))); //乘数的某一位 int add = 0; String temp = ""; //某个乘数位*被乘数 ---> 返回是一个字符串 for(int j=len_num1-1; j>=0; j--){ //遍历被乘数的每一位 int num1Cur = Integer.parseInt(String.valueOf(num1.charAt(j))); int mulCur = num1Cur * num2Cur + add; temp += String.valueOf(mulCur%10); add = mulCur/10; } if(add != 0){ temp += String.valueOf(add); } StringBuffer sb_temp = new StringBuffer(temp); StringBuffer temp_rev = sb_temp.reverse(); String str_temp ; str_temp = temp_rev.toString(); //末尾补充"0"; for (int z=0; z<times; z++) str_temp += "0"; sing_mul[i] = str_temp; times ++; //maxLen_sing --> 字符串数组sing_mul中元素的最大长度 if(sing_mul[i].length()>maxLen_sing) maxLen_sing = sing_mul[i].length(); } //将字符串数组中的所有元素相加。 String result = sing_mul[0]; for(int z=1; z<len_num2; z++){ int len_res = result.length(); //给短的字符串前补充"0". if(sing_mul[z].length()<len_res){ //字符串前部进行填充 //先反转字符串，补"0",再次反转字符串。 StringBuffer sb_z = new StringBuffer(sing_mul[z]); String sb_z_str = sb_z.reverse().toString(); for(int w=0; w<(len_res-sing_mul[z].length());w++) sb_z_str += "0"; StringBuffer sb_temp = new StringBuffer(sb_z_str); sing_mul[z] = sb_temp.reverse().toString(); } int add_ = 0; String temp_str = ""; for(int i=len_res-1; i>=0; i--){ int n1 = Integer.parseInt(String.valueOf(result.charAt(i))); int n2 = Integer.parseInt(String.valueOf(sing_mul[z].charAt(i))); int tep = n1+n2+add_; add_ = tep/10; temp_str += tep%10; } if(add_ != 0){ temp_str += String.valueOf(add_); } StringBuffer sb_temp_str = new StringBuffer(temp_str); result = sb_temp_str.reverse().toString(); } return result; } public static void main(String [] args){ Solution mulStr = new Solution(); String result = mulStr.multiply("9133","0"); System.out.print(result); } }
代码解释：
1. num1为被乘数，num2为乘数，用乘数的每一位去乘被乘数，得到一个字符串---》最终会得到字符串数组sig_mul，其中包含乘数位数个字符串
(注意:除了最后一个乘数位，其余的乘数位和被乘数相等得到的字符串应该在末尾补充相应位数的“0”）
2. sig_mul[0]中的字符串是最长的，因此result = sig_mul[0]
3. 每次使用result和sig_mul中的元素相加（1<=i<sig_mul.length）
(注意:每次相加之后的位数都会变化，但是以result的位数为准，因为它始终表示最长的位数)
（注意：每次使用sig_mul中的元素和result相加时，当sig_mul[i]的位数<result的位数时，应该给sig_mul[i]前补充相应位数的“0”，从而使得两个相加的字符串的位数相等，可以进行相加）
4. 在这个过程中会频繁的用到字符串reverse。
（因为每次相加或者相乘都是从字符串的末尾开始的，而正确的字符串应该是相乘或者相加结果的反转的字符串）
文中转化的方式是 String 转化 StringBuffer --》利用StringBuffer.reverse() --》StringBuffer 转化String
-----------------------------------------
部分问题未解决，后面更新。
[leetcode]multiply-strings java代码