LeetCode 043 字符串相乘

043 字符串相乘腾讯精选50
给定两个以字符串形式表示的非负整数 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）或直接将输入转换为整数来处理。

方法：倒序存储法
思路：
1.先找出两个数的位数相乘的关系，以首位为0，num[i]跟num[j]相乘存在num[i+j+1]里
LeetCode 043 字符串相乘
图来源https://blog.csdn.net/afei__/article/details/83891547
上面这个就是比较清晰的图

2.然后两个for循环，分别每个数相乘，for循环从最后（末尾）开始，让把每一位的数记下
3.然后一个for循环做进位操作
4.最后检查前面有多少个0，记下数量，然后从0后面开始转换成字符串

代码：

public static String multiply(String num1, String num2) {
        int[] num =new int[num1.length()+num2.length()];
        for (int i = num1.length()-1; i >=0; i--) {
            for (int j = num2.length()-1; j >=0; j--) {
                int a=num1.charAt(i)-'0';
                int b=num2.charAt(j)-'0';
                num[i+j+1]+=(num1.charAt(i)-'0')*(num2.charAt(j)-'0');
            }
        }
        //处理进位
        int temp=0;
        for (int i =num.length-1; i>=0 ; i--) {
            num[i]+=temp;
            temp=num[i]/10;
            num[i]%=10;
        }
        //处理最前面的0
        int a=0;
        while(a<num.length-1&&num[a]==0){
            a++;
        }
        String s="";
        for (int i = a; i <num.length ; i++) {
            s+=num[i];
        }
        return s;
    }

LeetCode 043 字符串相乘

相关推荐