字符串相乘算法

约定不等于承诺〃 2021-06-22 15:38 342阅读 0赞

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
    num1 和 num2 的长度小于110。
    num1 和 num2 只包含数字 0-9。
    num1 和 num2 均不以零开头，除非是数字 0 本身。
    不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理

实现代码如下
      public static void main(String[] args) { 
            
            String a=multiply("10", "222");
            System.out.println(a);
        }
        public static String multiply(String num1, String num2) { 
            if (num1 == null || num2 == null) { 
                return null;
            }
            if (num1.equals("0") || num2.equals("0")) { 
                return "0";
            }
    
            char[] chars1 = num1.toCharArray();
            char[] chars2 = num2.toCharArray();
            int length1 = chars1.length;
            int length2 = chars2.length;
            int[] resInts = new int[length1 + length2];
            int sum = 0;
    
            // 计算 结果数组 的 每一位的值
            for (int i = length1 - 1; i >= 0 ; i--) { 
                for (int j = length2 - 1; j >= 0; j--) { 
                    sum = (chars1[i] - '0') * (chars2[j] - '0') + resInts[i + j + 1];
                    resInts[i + j + 1] = sum % 10;  // 当前位 仅保存 计算结果的 个位
                    resInts[i + j] += sum/10;   // 进位值 += 就算值/10 （注意：此处的 进位值 的 ‘+=’ 操作是因为可能还有别的数组单元也会进到此位）
                }
            }
    
            // 将 int数组 转换为 字符串
            StringBuilder resStr = new StringBuilder();
            for (int i = 0; i < length1 + length2; i++) { 
                if (i == 0 && resInts[i] == 0) {     // 首位 不一定 进位
                    continue;
                }
                resStr.append(resInts[i]);
            }
            return resStr.toString();
        }