首页 > 代码库 > 43. Multiply Strings

43. Multiply Strings

2024-10-12 17:36:02   216人阅读

一、题目

　　1、描述

　　　　技术分享

　　2、题意

　　　　　将两个字符串表示的数字进行乘法计算，其中，若直接转换成整数计算会溢出。

 

二、解答

　　1、思路：

　　　　① 在 num2 中从后向前取出一个数字依次乘以num1，再进行相加

　　　　② 若 num2中逆数第二个数乘的结果后边需要加一个 0，第三个逆数则要加两个 0....

　　　　③ 可以直接用 StringBuilder， 最终将结果 reverse 即可。

　　

public String multiply(String num1, String num2) {
        
         if("0".equals(num1) || "0".equals(num2))
             return "0";
         
         int len1 = num1.length(), len2 = num2.length();
         StringBuilder sum = new StringBuilder("");
         for (int i = len2 - 1; i >= 0; i--) {
             StringBuilder sb = new StringBuilder();
             for(int j = (len2 - 1) - i; j > 0; j--) 
                 sb.append("0");
             
             int step = 0;
             char pos;
             for (int j = len1 - 1; j >= 0; j--) {
                int tmp = (num1.charAt(j) - ‘0‘) * (num2.charAt(i) - ‘0‘);
                
                pos = (char) (tmp % 10 + step + ‘0‘);
                step = tmp / 10;
                sb.append(pos);
             }
             if (step > 0)
                 sb.append(step);
             
             // add two nums;
             sum = addTwoStringNums(sum.toString(), sb.toString());
        }
         return sum.reverse().toString();
    }

    private StringBuilder addTwoStringNums(String num1, String num2) {
        
        int len1 = num1.length(), len2 = num2.length();
        int i = 0, j = 0;
        StringBuilder sb = new StringBuilder();
        int step = 0;
        char pos;
        while(i < len1 || j < len2) {
            int tmp = 0;
            if(i < len1) {
                tmp = (num1.charAt(i) - ‘0‘);
                i++;
            }
            if(j < len2) {
                tmp += (num2.charAt(j) - ‘0‘);
                j++;
            }
            tmp += step;
            pos = (char) (tmp % 10 + ‘0‘);
            sb.append(pos);
            step = tmp / 10;
        }
        if(step > 0)
            sb.append(step);
        
        return sb;
    }

 

　　方法二：  每个乘数的单个数字相乘，对应的位置 下标有规律，参考 LeetCode 大神，贴图：

　　　　　　

技术分享

　　

代码如下： 

public static String multiply2(String num1, String num2) {
        int len1 = num1.length();
        int len2 = num2.length();
        
        int[] pos = new int[len1 + len2];
        for(int i = len1 - 1; i >= 0; i--)
            for(int j = len2 - 1; j >= 0; j--) {
                int tmp = (num1.charAt(i) - ‘0‘) * (num2.charAt(j) - ‘0‘);
                int p1 = i + j, p2 = i + j + 1;
                int sum = tmp + 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();
    }

 

43. Multiply Strings


联系
我们