leetcode:43. 字符串相乘

客官°小女子只卖身不卖艺 2022-04-13 14:41 185阅读 0赞

## 题目: ##

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

示例 1:

输入: num1 = “2”, num2 = “3”  
输出: “6”  
示例 2:

输入: num1 = “123”, num2 = “456”  
输出: “56088”  
说明：

num1 和 num2 的长度小于110。  
num1 和 num2 只包含数字 0-9。  
num1 和 num2 均不以零开头，除非是数字 0 本身。  
不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

## 分析: ##

两者相乘最大长度不会超过两个字符串长度之和,构造一个长度为两个字符串长度之和的数组分别添加每一位相乘的值,再处理进位即可

## 代码: ##

public String multiply(String num1, String num2) {
    		char[] char1 = num1.toCharArray();
    		char[] char2 = num2.toCharArray();
    		int l1 = char1.length;
    		int l2 = char2.length;
    		
    		if(l1==1&&char1[0]=='0'||l2==1&&char2[0]=='0')
    			return "0";
    
    		int[] res = new int[l1 + l2];
    		// 每一位分别相乘放到res数组内
    		for (int i = 0; i < l1; i++) {
    			for (int j = 0; j < l2; j++) {
    				res[l1 + l2 - 2 - i - j] += (char1[i] - '0') * (char2[j] - '0');
    			}
    		}
    		// 处理进位
    		int current = 0;
    		while (current < l1 + l2 - 1) {
    			if (res[current] > 9) {
    				res[current + 1] += res[current] / 10;
    				res[current] %= 10;
    			}
    			current++;
    		}
    
    		StringBuffer sb = new StringBuffer();
    		// 处理数组前0不进入结果集
    		boolean start = false;
    		for (int i = l1 + l2 - 1; i >= 0; i--) {
    			if (start) {
    				sb.append(res[i]);
    			} else if (res[i] != 0) {
    				start = true;
    				sb.append(res[i]);
    			}
    		}
    		return sb.toString();
    	}

## 效率: ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0NTE2NTQ5_size_16_color_FFFFFF_t_70]

## 总结: ##

待优化

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0NTE2NTQ5_size_16_color_FFFFFF_t_70]: /images/20220413/514705068700454298c40897acb73acc.png