时间戳

首页 > 解决方案 > 在不使用 Big-Integer 库的情况下将大字符串数相乘

java - 在不使用 Big-Integer 库的情况下将大字符串数相乘

问题描述

我编写了一个简单的解决方案，它将以字符串形式给出的 2 个整数相乘并将乘积作为字符串返回。但它不适用于大值，我不允许使用 Big-Integer 库。

这是我目前的解决方案。

class Solution {
    public String multiply(String num1, String num2) {
        int numOne = 0;
        int numTwo = 0;
        
        for(char c : num1.toCharArray()){
            if((int)(c-'0') >= 0 && (int)(c-'0') <= 9){
                numOne = numOne*10 + (int)(c-'0');
            }
        }

        for(char c : num2.toCharArray()){
            if((int)(c-'0') >= 0 && (int)(c-'0') <= 9){
                numTwo = numTwo*10 + (int)(c-'0');
            }
        }
        
        return numOne*numTwo + "";
    }
}

我在以下测试用例中遇到错误：

Input:
"123456789"
"987654321"
Output:
"-67153019"
Expected:
"121932631112635269"

我应该进行哪些更改才能使大数也相乘？

标签： javastring

解决方案

为此，您可以参考 Karatsuba 乘法算法。

你也可以这样做。

  1. 如果任何数字为负数，则从子字符串 1 到 n。
  2. 从第二个数字的最后一位开始。
  3. 将它与第一个数字相乘。存储结果。
  4. 对第二个数字的所有数字执行此操作，并继续将上一步的结果添加到当前步骤，并在位置上移动第 i 个。

互联网上也有此解决方案的示例。你会找到它的。

推荐阅读