每日力扣：43. 字符串相乘

素颜马尾好姑娘i 2022-02-27 00:58 193阅读 0赞

package com.sample.suncht.algo;
 
 import java.util.ArrayList;
 import java.util.List;
 
 /**
 * 43. 字符串相乘
 * 
 * 给定两个以字符串形式表示的非负整数 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 class Multiply43 {
 public String multiply(String num1, String num2) {
 char[] chars1 = num1.toCharArray();
 char[] chars2 = num2.toCharArray();
 
 if((chars1.length == 1 && chars1[0]=='0') || (chars2.length == 1 && chars2[0]=='0')) {
 return "0";
 }
 
 char[] result = new char[chars1.length + chars2.length];
 
 for (int i = 0; i < result.length; i++) {
 result[i] = '0';
 }
 
 for (int i = chars1.length - 1; i >= 0; i--) {
 this.multiply(chars1[i], chars1.length - i - 1, chars2, result);
 }
 
 int indexNoZero = 0;
 for (int i = 0; i < result.length; i++) {
 if(result[i] != '0') {
 indexNoZero = i;
 break;
 }
 }
 return new String(result, indexNoZero, result.length - indexNoZero);
 }
 
 //相乘
 private void multiply(char c, int digit, char[] chars, char[] result) {
 int value;
 if(c=='0') {
 return;
 }
 
 for (int i = chars.length - 1; i >= 0; i--) {
 value = (c - '0') * (chars[i] - '0');
 
 this.add(result, digit + chars.length - i - 1, value);
 }
 
 }
 
 //相加
 private void add(char[] result, int digit, int value) {
 if(value <= 0) {
 return;
 }
 int sum = (result[result.length - 1 - digit] - '0') + value;
 
 result[result.length - 1 - digit] = (char)(sum % 10 + '0');
 //处理进位
 while (sum >= 10) {
 sum = sum / 10;
 this.add(result, digit + 1, sum);
 }
 }
 
 public static void main(String[] args) {
 
 List<AlgoHelper.BiInputParams<String, String, String>> datas = new ArrayList<>();
 datas.add(new AlgoHelper.BiInputParams<>("20", "3000", "60000"));
 datas.add(new AlgoHelper.BiInputParams<>("123", "456", "56088"));
 datas.add(new AlgoHelper.BiInputParams<>("987", "258", "254646"));
 datas.add(new AlgoHelper.BiInputParams<>("10", "123", "1230"));
 datas.add(new AlgoHelper.BiInputParams<>("1234567890", "9876543210", "12193263111263526900"));
 datas.add(new AlgoHelper.BiInputParams<>("0", "0", "0"));
 AlgoHelper.assertResult(datas, new Multiply43()::multiply);
 }
 }