字符串乘法

[编程题]字符串乘法

热度指数：9726 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给出两个用字符串表示的数字，将两个数字的乘积作为字符串返回。
备注：数字可以无限大，且是非负数。

示例1

输入

"1","2"

输出

"2"

算法知识视频讲解

Java

tornado123

/** 
字符串相乘 - 即 大数相乘， 用模拟乘法累加法
 */
public class StringMultiplication {
    /**
     *
     * @param num1 string字符串
     * @param num2 string字符串
     * @return string字符串
     */
    public String multiply (String num1, String num2) {
        int len_num1 = num1.length();
        int len_num2 = num2.length();
        // 长度为 len_num1 + len_num2 的结果数据，用来存放结算的乘积的值
        int[] result = new int[len_num1 + len_num2];
        Arrays.fill(result, 0);
        /*
        先不考虑进位问题，根据竖式的乘法运算，num1的第i位与num2的第j位相乘，结果应该存放在结果的第i+j位上
        为了方便，从
        */
        for (int i = len_num1 - 1; i >= 0; i--) {
            for (int j = len_num2 - 1; j>= 0; j--) {
                // 因为 num1 、num2 的高位都是从 0 开始数的，所以存储结果的时候，存在 i + j + 1 的索引下
                result[i + j + 1] += (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
            }
        }
        // 单独处理 result 中的进位问题. 从低位 --> 高位 (从 result 的 右 -> 左)
        for (int i = result.length - 1; i > 0; i--) {
            if (result[i] >= 10) {
                result[i -1] += result[i] / 10;
                result[i] %= 10;
            }
        }
        // int[] -> String
        StringBuffer sb = new StringBuffer();
        int i = 0;
        while (result[i] == 0 && i < result.length - 1) {
            i ++;
        }
        while (i < result.length) {
            sb.append(result[i++]);
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        String num1 = "0";
        String num2 = "0";
        System.out.println(new StringMultiplication().multiply(num1, num2));
    }
}

发表于 2020-09-20 22:00:30 回复(0)

Java

悟Kong

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);
    }
}

发表于 2020-04-18 17:56:31 回复(0)

Java

齐鱼鱼

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

发表于 2018-09-22 14:46:22 回复(2)

Java

Holiday_12138

public class Solution {
    public String multiply(String num1, String num2) {
        StringBuffer m1 = new StringBuffer(num1.length() > num2.length() ? num1 : num2);
        StringBuffer m2 = new StringBuffer(num1.length() > num2.length() ? num2 : num1);
		int i = m2.length() - 1;
		StringBuffer res = new StringBuffer();
		while(i >= 0) {
			res = add(res,times(m1, m2.charAt(i)-'0'));
			m1.append('0');
			i--;
		}
		return res.toString();
    }
    
    public StringBuffer add(StringBuffer sb1, StringBuffer sb2) {
        int i = sb1.length() - 1;
        int j = sb2.length() - 1;
        int sum;
        int carry = 0;
        StringBuffer res = new StringBuffer();
        while(i >= 0 && j >= 0) {
            sum = carry + sb1.charAt(i) + sb2.charAt(j) - '0' - '0';
            carry = sum / 10;
            res.append(sum % 10);
            i--;
            j--;
        }
        while(i >= 0) {
            if(carry != 0) {
            	sum = sb1.charAt(i) - '0' + carry;
                res.append(sum % 10);
            	carry = sum / 10;
            }
            else
                res.append((sb1.charAt(i) - '0') % 10);
            i--;
        }
        while(j >= 0) {
            if(carry != 0) {
            	sum = sb2.charAt(j) - '0' + carry;
                res.append(sum % 10);
                carry = sum / 10;
            }
            else
                res.append((sb2.charAt(j) - '0') % 10);
            j--;
        }
        if(carry != 0)
            res.append(carry % 10);
        return res.reverse();
    }
    
    public StringBuffer times(StringBuffer sb, int n) {
       	StringBuffer res = new StringBuffer();
        if(n == 0) {
			res.append('0');
			return res;
		}
		int i = sb.length() - 1;
		int carry = 0;
		while(i >= 0) {
			int sum = (sb.charAt(i)-'0') * n + carry;
			res.append(sum % 10);
			carry = sum / 10;
			i--;
		}
		if(carry != 0)
	            res.append(carry % 10);
    	return res.reverse();
    }
}

发表于 2017-06-11 21:04:57 回复(0)

Java

城市里的养猫者

Remember how we do multiplication?

Start from right to left, perform multiplication on every pair of digits, and add them together. Let's draw the process! From the following draft, we can immediately conclude:

`num1[i] * num2[j]` will be placed at indices `[i + j`, `i + j + 1]`

Here is my solution. Hope it helps!

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();
}

发表于 2017-03-12 14:45:57 回复(0)

Java

詆調壹點

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

发表于 2016-11-05 21:39:00 回复(3)