字符串乘法

import java.util.*;
import java.math.*;


public class Solution {
    /**
     * 
     * @param num1 string字符串 
     * @param num2 string字符串 
     * @return string字符串
     */
    public String multiply (String num1, String num2) {
        if(num1.equals("0") || num2.equals("0")){
            return "0";
        }
        int size1 = num1.length();
        int size2 = num2.length();
        int[] result = new int[size1 + size2];
        StringBuilder sb = new StringBuilder();
        //分别交叉计算两个数字的乘积，并存入数组保存
        for(int i = size1 - 1; i >= 0; i--){
            for(int j = size2 - 1; j >= 0; j--){
                result[i + j + 1] += (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
            }
        }
        //根据进位进行相加
        int b = 0;
        for(int i = result.length - 1; i >= 0; i--){
            //当前乘积加上一组数据的进位
            result[i] += b;
            //下次的进位值
            b = result[i] / 10;
            //去掉进位后的值
            result[i] = result[i] % 10;
        }
        //去掉开头的0
        int index = 0;
        for(int i = 0; i < result.length; i++){
            if(result[i] != 0){
                index = i;
                break;
            }
        }
        //拼接成字符串
        for(int i = index; i < result.length; i++){
            sb.append(result[i] + "");
        }
        return sb.toString();
    }
}

class Solution {
public:
    string mul(string num1,int m){//计算一个字符串和一个个位数的乘积
        
        int n=num1.size();
        int t=0;
        for(int i=n-1;i>=0;i--){
            int val=(num1[i]-'0')*m+t;
            t=val/10;
            num1[i]='0'+val%10;
        }
        if(t>0)
            num1.insert(num1.begin(),'0'+t);
        return num1;
    }
    string add(string num1,string num2){//计算两个字符串的和
        if(num1.size()<num2.size()){
            string tmp=num1;
            num1=num2;
            num2=tmp;
        }
        num2.insert(num2.begin(),num1.size()-num2.size(),'0');
        
        int t=0;
        for(int i=num1.size()-1;i>=0;i--){
            int val=num1[i]-'0'+num2[i]-'0'+t;
            t=val/10;
            num1[i]=val%10+'0';
        }
        if(t>0)
            num1.insert(num1.begin(),t+'0');
        return num1;
    }
    string multiply(string num1, string num2) {
        
        if(num1.size()<num2.size()){
            string tmp=num1;
            num1=num2;
            num2=tmp;
        }
        string res;
        for(int i=0;i<num2.size();i++){//类似于sum=sum*10*x
            res.insert(res.begin()+res.size(),'0');
            res=add(res,mul(num1,num2[i]-'0'));
            
        }
        int i=0;
        while(i<res.size()&&res[i]=='0')//经过上面的计算后，有可能在字符串的开始位置有0
            i++;
        if(i>=res.size())//如果结果全是为0
            return "0";
        else//否则从第一个非0位置开始算起
            return res.substr(i);
        
    }
};

class Solution {
public:
    string multiply(string num1, string num2) {
        int m = num1.length();
        int n = num2.length();
        int c = 0;
        string r(m+n, '0');
        for(int i=m-1;i>=0;i--)
        {
        	int a = num1[i]-'0';
        	for(int j=n-1;j>=0;j--)
        	{
        		int b = num2[j]-'0';
        		int d = r[i+j+1]-'0';
        		int x = a*b + d + c;
        		r[i+j+1] = x%10+'0';
        		c = x/10;
			}
			if(c)
			{
				r[i] = c+'0';
				c = 0;
			}
		}
		int k = 0;
		while(k<r.size() && r[k]=='0')
			k++;
		return k==r.size()?"0":r.substr(k);
    }
};

//来一个纯模拟手工运算的方法。
//先列出梯形的乘法步骤
//再对应相加，然后进位。
//从高位往低位找第一个不为0个数字，因为临时数组初始化的时候都是0.
//最后将这些数字转化为字符串。
//4ms AC,看来也不慢。
class Solution {
public:
string multiply(string num1, string num2) {
    if(num1 == "0" || num2 == "0")
        return "0";
    vector<int> arr(num1.size() + num2.size() , 0);
    string ans = "";
    char tmp = '0';
    for (int i = num1.size() - 1; i >= 0; --i)
        for (int j = num2.size() - 1; j >= 0; --j) {
            arr[i + j + 1] += (num1[i] - '0')*(num2[j] - '0');
        }
    for(int i = arr.size()-1; i > 0 ; --i){
        arr[i-1] += arr[i] / 10;
        arr[i] = arr[i] % 10;
    }
    int i = 0;
    while(arr[i] == 0) ++i;
    while(i != arr.size()){
        tmp = arr[i] + '0';
        ans += tmp;  
        ++i;
    }
    return ans;
}
};

class Solution {
public:
    string multiply(string num1, string num2) {
 	vector<int> v(num1.length()+num2.length(),0); 	
 	for(int i=0;i<num1.length();i++){
 		for(int j=0;j<num2.length();j++){
 			v[i+j]+=(num1[i]-'0')*(num2[j]-'0');
 		}
 	}
 	int carry=0;
 	for(int j=v.size()-1;j>=1;j--){
 		v[j]=(carry+v[j-1])%10;
 		carry=(carry+v[j-1])/10;
 	}
	if (carry != 0)
		v[0] = carry;
	else
		v[0] = -1;
 	string s="";
 	for(auto i:v){
 		if(i>=0)
 			s+=i+'0';
 	}
	if (s[0] == '0')
		s = "0";
 	return s;
}
};

 package go.jacob.day721;
/**
 * 43. Multiply Strings
 * @author Jacob
 *
 */
public class Demo1 {
	/*
	 * 大数相乘
	 * Runtime: 21 ms.Your runtime beats 99.95 % of java submissions.
	 * 用空间换时间：如果有空间要求的话，可以不建立arr1和arr2数组，直接在计算的时间用num1.charAt(i)-'0'即可
	 */
	public String multiply(String num1, String num2) {
		if (num1 == null || num2 == null || num1.length() == 0 || num2.length() == 0)
			return null;
		if(num1.equals("0")||num2.equals("0"))
			return "0";
		int len1 = num1.length(), len2 = num2.length();
		int[] arr1 = new int[len1], arr2 = new int[len2];
		// 首尾交换，便于计算
		for (int i = 0; i < len1; i++) {
			arr1[len1 - 1 - i] = num1.charAt(i) - '0';
		}
		for (int i = 0; i < len2; i++) {
			arr2[len2 - 1 - i] = num2.charAt(i) - '0';
		}
		// 两数相乘结果的长度介于len1*len2-1到len1*len2
		int[] res = new int[len1 + len2];
		for (int i = 0; i < len1; i++) {
			for (int j = 0; j < len2; j++) {
				res[i + j] += arr1[i] * arr2[j];
			}
		}
		for (int i = 0; i < len1 + len2; i++) {
			while (res[i] >9) {
				res[i + 1] += res[i] / 10;
				res[i] = res[i] % 10;
			}
		}
		StringBuilder ans=new StringBuilder();
		for (int i = len1 + len2-1; i >=0; i--) {
			ans.append(res[i]);
		}
		//如果第一个元素是0，去除
		return ans.charAt(0) == '0' && ans.length() != 1 ? ans.substring(1) : ans.toString();
	}
}

import java.math.BigDecimal;
public class Solution {
    public String multiply(String num1, String num2) {
		return new BigDecimal(num1).multiply(new BigDecimal(num2)).toString();
	}
}

    public String multiply(String num1, String num2) {
        int n1 = num1.length();
        int n2 = num2.length();
        StringBuilder sb = new StringBuilder();
        int[] tmp = new int[n1+n2];
        
        for(int i=n1-1;i>=0;i--){
            for(int j=n2-1;j>=0;j--){
                tmp[i+j+1] +=(num1.charAt(i)-'0')*(num2.charAt(j)-'0');
            }
        }
        int carrybit=0;//从个位开始，carrybit是进位
        for(int i=tmp.length-1;i>=0;i--){
            tmp[i]+=carrybit;
            carrybit=tmp[i]/10;
            tmp[i]=tmp[i]%10;
            
        }
        int left=0;
        while(left<tmp.length-1&&tmp[left]==0)
            left++;
        for(;left<tmp.length;left++){
            sb.append(tmp[left]);
        }
        return sb.toString();    
    }

class Solution {
public:
	string multiply(string num1, string num2) {
		int carry = 0;
		string result(num1.size()+num2.size(),'0');
		for (int i=num1.size()-1;i>=0;--i) {
			int a = num1[i] - '0';
			for (int j=num2.size()-1;j>=0;--j) {
				int b = num2[j] - '0';
				int c = result[i+j+1] - '0';
				int v = a*b+c+carry;
				result[i+j+1] = v%10 + '0';
				carry = v/10;
			}
			if(carry){
				result[i] = carry+'0';
				carry = 0;
			}
		}
		int i = 0;
		while (i<result.size()&&result[i]=='0') ++i;
		return i==result.size()?"0":result.substr(i);
	}
};

基本思路：

1. 首先开辟一个长度为num1.size()+num2.size()的由0填充的新字符串
2. 然后从num2的尾部向头部遍历，每次遍历都与num1求和，将结果保存到新字符串中
3. 去除新字符串的前缀0，即为最终结果

代码如下：

//
// Created by jt on 2020/9/29.
//
#include <string>
using namespace std;

class Solution {
public:
    /**
     *
     * @param num1 string字符串
     * @param num2 string字符串
     * @return string字符串
     */
    string multiply(string num1, string num2) {
        // write code here
        string res = string(num1.size() + num2.size(), '0');
        int idx = num1.size()+num2.size()-1;
        for (int i = num2.size()-1; i >= 0; --i) {
            // offset保存res当前元素离末尾元素的偏移量，carry保存进位
            int offset, carry = 0, digit = num2[i] - '0';
            for (int j = num1.size()-1; j >= 0; --j) {
                offset = (num1.size()-1-j)+(num2.size()-1-i);
                int a = digit * (num1[j]-'0') + carry + res[idx-offset]-'0';
                res[idx-offset] = a % 10 + '0';
                carry = a / 10;
            }
            if (carry != 0) res[idx-offset-1] = carry + '0';
        }
        int begin = 0;
        while(begin < res.size() && res[begin] == '0') ++begin;
        if (begin == res.size()) return "0";
        else return res.substr(begin);
    }
};

public class Solution {
    public String multiply(String num1, String num2) {
        if(num1.equals("0")||num2.equals("0"))
        return "0";
        if(num1.length()<num2.length()){
            String temp=num1;
            num1=num2;
            num2=temp;
        }
        String[] s=new String[num2.length()];
        for(int i=0;i<s.length;i++){
            s[i]="";
        }
        String res="";
        for(int i=num2.length()-1;i>=0;i--){
            int index=0;
            int n2=Integer.valueOf(String.valueOf(num2.charAt(i)));
            for(int j=num1.length()-1;j>=0||index!=0;j--){
                if(j>=0){
                    int n1=Integer.valueOf(String.valueOf(num1.charAt(j)));
                    int sum=n1*n2+index;
                    index=sum/10;
                    int y=sum%10;
                    s[num2.length()-1-i]=String.valueOf(y)+s[num2.length()-1-i];
                }
                else{
                    s[num2.length()-1-i]=String.valueOf(index)+s[num2.length()-1-i];
                    index=0;
                }
            }   
        }
        for(int i=0;i<s.length;i++){
            for(int j=i;j>0;j--){
                s[i]=s[i]+"0";
            }
        }
        int index=0;
        for(int i=0;i<num1.length()+num2.length();i++){
            int sum=0;
            sum=sum+index;
            for(int j=0;j<s.length;j++){
                if(s[j].length()-i-1>=0){
                sum=sum+Integer.valueOf(String.valueOf(s[j].charAt(s[j].length()-i-1)));
                }
            }
            index=sum/10;
            res=String.valueOf(sum%10)+res;
        }
        int i=0;
        while(i<res.length()&&res.charAt(i)=='0'){
            i++;
        }
    	return res.substring(i);
    }
}

class Solution {
public:
    string multiply(string num1, string num2) {
        int n1 = num1.length();
        int n2 = num2.length();
        vector<int> temp(n1 + n2, 0);
        for (int i = n1 - 1;i >= 0;i--) {
            for (int j = n2 - 1;j >= 0;j--) {
                temp[i + j + 1] += (num1[i] - '0') * (num2[j] - '0');
            }
        }
        int carry = 0;
        for (int index = temp.size() - 1;index >= 0;index--) {
            temp[index] = temp[index] + carry;
            carry = temp[index] / 10;
            temp[index] = temp[index] % 10;
        }
        int left = 0;
        while (left < temp.size() && temp[left] == 0) {
            left++;
        }
        string res;
        for (;left < temp.size();left++) {
            res.append(1, temp[left] + '0');
        }
        return res.length() != 0 ? res : "0";
    }
};

string multiply(string num1, string num2) {
        if(num1=="0"||num2=="0")
            return "0";
        int n1=num1.length(),n2=num2.length();
        vector<vector<int>> multiply(n2,vector<int>(n1+n2-1));
        for(int i=0;i<n1;i++)
            for(int j=0;j<n2;j++){
                multiply[j][j+i]=(num1[n1-i-1]-'0')*(num2[n2-j-1]-'0');
            }
        string res="";
        int pre=0;
        for(int i=0;i<n1+n2-1;i++){
            int num=pre;
            for(int j=0;j<n2;j++){
                num+=multiply[j][i];
            }
            res.push_back('0'+num%10);
            pre=num/10;
        }
        while(pre!=0){
            res.push_back('0'+pre%10);
            pre/=10;
        }
        reverse(res.begin(),res.end());
        return res;
    }

public class MultiplyStrings {
    public String multiply(String num1, String num2) {
        int m=num1.length(),n=num2.length();
        int[] pos= new int[m+n];
        for(int i=m-1;i>=0;i--){
            for(int j=n-1;j>=0;j--){
                int mul=(num1.charAt(i)-'0')*(num2.charAt(j)-'0');
                int p1=i+j,p2=i+j+1;
                int sum=mul+pos[p2];
                                 pos[p1]+=sum/10;
                pos[p2]=(sum)%10;
            }
        }
        StringBuilder sb=new StringBuilder();
        for(int p:pos){
            if(!(sb.length() == 0 && p == 0)){
                sb.append(p);
            }
        }
        return sb.length()==0?"0":sb.toString();
    }
}

raodanwoyiranxihuanni

class Solution {
public:
string multiply(string num1, string num2) {
int len1 = num1.size();
int len2 = num2.size();
if (len1 == 0 || len2 == 0 || num1 == "0" || num2 == "0") return "0";
vector<int > temp(len1 + len2 + 1, 0);

    for (int i = 0; i < len1; ++i)
    {
        for (int j = 0; j < len2; ++j)
        {
            temp[i + j + 2] += (num1[i] - '0') * (num2[j] - '0');
        }
    }

    int c = 0;//进位
    for (int i = temp.size() - 1; i >= 0; i--)
    {
        int num = temp[i] + c;
        temp[i] = num % 10;
        c = num / 10;
    }
    int nozeroindex = 0;
    for (; nozeroindex < temp.size(); ++nozeroindex)
    {
        if (temp[nozeroindex] != 0)
            break;
    }

    string res;
    for (int i = nozeroindex; i < temp.size(); ++i)
    {
        res += char(temp[i] + '0');
    }
    return res;
}

};

//一言不合就超时……
class Solution {
public:     
    string mul(string s,int l,int m)
    {
        int cari=0;
        for(int i=l-1;i>=0;i--)
        {
            int tp=(s[i]-'0')*m+cari;
            cari=tp/10;
            s[i]='0'+tp%10;
        }
        if(cari>0)
            s=char(cari+'0')+s;
        return s;
    }
    string addi(string s1,string s2,int l)
    {
        int l2 = s2.length();
        for (int i = 0; i < l - l2; i++)
            s2 = '0' + s2;
        string cari="";
        string ad="";
        bool co=false;
        for(int i=0;i<l;i++)
        {
            int tp=s1[i]-'0'+s2[i]-'0';
            if(tp>=10)
                co=true;
            ad+=tp%10+'0';
            cari+=tp/10+'0';
        }
        if(!co)        
            return ad;

        ad='0'+ad;
        cari+='0';
        return addi(ad,cari,l+1);
    }
    string core(string s1,string s2,int l1,int l2)
    {
        string out="";
        for(int i=0;i<l2;i++)
        {
            int m=s2[i]-'0';
            string tp=mul(s1,l1,m);
            if(out.empty())
                out=tp;
            else
            {
                out+='0';
                out=addi(out,tp,out.length());
            }
        }
        int j=0;
        while(j<out.length()&&out[j]=='0')
            j++;
        return out.substr(j);
    }
    string multiply(string num1, string num2) {

        int l1=num1.length();
        int l2=num2.length();
       if (l1 == 0 || l2 == 0)
           return "";
        if (num1 == "0" || num2 == "0")
            return "0";
        if (num1 == "1")
            return num2;
        if (num2 == "1")
            return num1;
        if(l1>l2)
            return core(num1,num2,l1,l2);

       return core(num2,num1,l2,l1);
    }
};

public static String multiply(String num1, String num2) {

        int[][] result = new int[Math.max(num1.length(), num2.length())][(num1.length() + num2.length()) + 1];
        int sign = 0, index1 = 0, index2 = result[0].length - 1;
        int[] multiplyResult = new int[num1.length() + num2.length() + 1];
        int index = multiplyResult.length - 1;

        for (int i = num1.length() - 1; i >= 0; i--) {
            int a = num1.charAt(i) - '0';
            for (int j = num2.length() - 1; j >= 0; j--) {
                int b = num2.charAt(j) - '0';
                result[index1][index2] = (a * b + sign) % 10;
                sign = (a * b + sign) / 10;
                index2--;
            }
            if (index2 >= 0 && sign != 0) {
                result[index1][index2] = sign;
            }
            index1++;
            index2 = result[0].length - index1 - 1;
            sign = 0;
        }

        sign = 0;

        //相加
        for (int i = result[0].length - 1; i >= 0; i--) {
            int sum = 0;
            for (int j = 0; j < result.length; j++) {
                sum += result[j][i];
            }
            int a = (sum + sign) % 10;
            sign = (sum + sign) / 10;
            multiplyResult[index] = a;
            index--;
        }
        //算上符号位
        if (sign > 0) {
            multiplyResult[index] = sign;
        }

        StringBuilder sb = new StringBuilder();
        //补偿最后index--;
        index++;
        while (index >= 0 && multiplyResult[index] == 0) {
            index++;
            //如果所有的都为0
            if (index == multiplyResult.length)
                return "0";
        }

        //得到结果
        for (int i = index; i < multiplyResult.length; i++) {
            sb.append(multiplyResult[i]);
        }

        return sb.toString();

    }