LeetCode字符串相乘【大数乘法】

今天药忘吃喽~ 2022-09-10 01:28 191阅读 0赞

# 1 字符串相乘 #

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

# 2 解决方法 #

## 2.1 加法 ##

**思路：** 先乘在加。

public String multiply(String num1, String num2) { 
            if (num1.equals("0") || num2.equals("0")) { 
                return "0";
            }
    
            //存结果
            String rs = null;
            int i = num1.length() - 1;
            //遍历第一个数
            while (i >= 0) { 
                //存临时结果
                StringBuilder temp = new StringBuilder();
                int j = num2.length() - 1;
                //获取第一个个数
                int temp1 = num1.charAt(i) - '0';
                int carry = 0;
                //遍历第二个数，并且计算结果
                while (j >= 0 || carry != 0) { 
                    int temp2 = j >= 0 ? num2.charAt(j) - '0' : 0;
                    int num = temp1 * temp2 + carry;
                    temp.append(num % 10);
                    carry = num / 10;
                    j--;
                }
                //翻转并且补0
                StringBuilder reverse = temp.reverse();
                for (int k = i; k < num1.length() - 1; k++) { 
                    reverse.append("0");
                }
                //大数相加
                if (rs == null) { 
                    rs = reverse.toString();
                } else { 
                    rs = addString(rs, reverse.toString());
                }
                i--;
            }
    
    
            return rs;
        }
    
        private String addString(String num1, String num2) { 
            StringBuilder rs = new StringBuilder();
            int i = num1.length() - 1;
            int j = num2.length() - 1;
            int carry = 0;
            while (i >= 0 || j >= 0 || carry != 0) { 
                int temp1 = i >= 0 ? num1.charAt(i) - '0' : 0;
                int temp2 = j >= 0 ? num2.charAt(j) - '0' : 0;
                int num = temp1 + temp2 + carry;
                rs.append(num % 10);
                carry = num / 10;
    
                i--;
                j--;
            }
            return rs.reverse().toString();
        }
    }

## 2.2 优化竖式 ##

**思路**:设 num1 的长度为m ，num2的长度为n，那么m\*n的最大位数为 m+n 或 m+n-1

public String multiply(String num1, String num2) { 
            //如果存在一个0
            if (num1.equals("0") || num2.equals("0")) { 
                return "0";
            }
            //设 num1 的长度为m ，num2的长度为n，那么m*n的最大位数为 m+n 或 m+n-1
            int[] rs = new int[num1.length() + num2.length()];
            for (int i = num1.length() - 1; i >= 0; i--) { 
                int x = num1.charAt(i) - '0';
                for (int j = num2.length() - 1; j >= 0; j--) { 
                    int y = num2.charAt(j) - '0';
                    //低位总和
                    int sum = x * y + rs[i + j + 1];
                    //低位
                    rs[i + j + 1] = sum % 10;
                    //高位，高位不用考虑进位问题
                    rs[i + j] = sum / 10 + rs[i + j];
    
                }
            }
            StringBuilder sb = new StringBuilder();
            int index = rs[0] == 0 ? 1 : 0;
            while (index < rs.length) { 
                sb.append(rs[index++]);
            }
            return sb.toString();
        }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_20_color_FFFFFF_t_70_g_se_x_16]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/1c62c819484842f58fb3d5f8047e1615.png