Decorative image frame

Geooo的博客

(王兆祺の个人博客)

Geooo的博客

leetcode 43 字符串相乘 java

题目

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
输入: num1 = “123”, num2 = “456”
输出: “56088”


思路

//类比于高精度乘法的做法，用一个整数数组res[]，数组的每一位用来保存乘法结果的某一位，比如res[0]表示个位，res[1]表示十位


//然后用第二个数的每一位乘以第一个数，结果存到res中，注意对准位置，最后如果有进位的话，要再往高位累加。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
//43.字符串相乘
	public String multiply(String num1, String num2) {
		if(num1.equals("0") || num2.equals("0"))//特殊情况
			return "0";
		
		int n = num1.length(), m = num2.length();
		//一般来说两个数相乘，其最大位数也不会大于啷个位数之和
		int[] res = new int[n + m];
		char[] nums1 = num1.toCharArray();
		char[] nums2 = num2.toCharArray();
		//字符转换为数字
		for(int i =0; i<nums1.length; i++)
			nums1[i] -= '0';
		for(int i =0; i<nums2.length; i++)
			nums2[i] -= '0';
		
	
		//用第二个数的每一个数  乘以 第一个数，结果存到数组里，并注意处理进位
		for(int i =0; i<m; i++) {
			int carry = 0;
			for(int j =0; j<n; j++) {
				res[i + j] = res[i+j] + nums2[m-1-i] * nums1[n-1-j] + carry;
				carry = res[i+j] / 10;
				res[i+j] %= 10;
			}
			//处理进位
			int k = i+n;
			while(carry > 0) {
				res[k] += carry;
				carry = res[k] /10;
				res[k] = res[k] % 10;
				k++;
			}
		}
		
		StringBuffer sb = new StringBuffer();//使用String或者StringBuffer都可以，但StringBuffer效率更高
		int i = n + m - 1;
		while(i >= 0 && res[i] == 0)
			i--;
		while(i >= 0) {
			sb.append(res[i]);
			i--;
		}
		
		return sb.toString();
    }