字符串相乘——大整数乘法

概述

给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积也表示为字符串形式。

输入: num1 = “2”, num2 = “3”
输出: “6”

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/multiply-strings
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

常规思路: 1234 * 456 = 1234 * 6 + 1234 * 50 + 1234 * 400

由于 0 乘以任何数都是 0,所以 1234 * 50 = 1234 * 5 的结果加上一个 0,1234 * 400 的结果等于 1234 * 4 的结果结尾加上两个 0;

其次将计算结果相加,又用到了字符串的加法实现;字符串的加法实现也是类似,从末位开始相加,超过 10 就进位。

实现

class Solution {
    public String multiply(String num1, String num2) {

        if ("0".equals(num1) || "0".equals(num2)){
            return "0";
        }
        int count = 0; // 表示第几次循环,用于字符串结尾加 0 
        String answer = "0"; 
        for (int i = num2.length() - 1; i >= 0 ; i--) {  // 从 num2 的末尾开始,与 num1 的各个位相乘
            char tempNum2 = num2.charAt(i);
            int jinwei = 0;  // 进位
            StringBuilder stringBuilder = new StringBuilder();
            int tempNum2Int = tempNum2 - '0';  
            for (int j = num1.length() - 1; j >= 0 ; j--) {  // 将 num1 的各位与 num2 的当前字符相乘
                int tempNum1Int = num1.charAt(j) - '0';
                int result = tempNum2Int * tempNum1Int + jinwei;  // 
                stringBuilder.append(result % 10);
                jinwei = result / 10;
            }
            if (jinwei > 0){
                stringBuilder.append(jinwei);
            }
            stringBuilder = stringBuilder.reverse();
            // 结尾加 0 
            for (int j = 0; j < count; j++) {
                stringBuilder.append("0");
            }
            count++;
            // 大整数加法
            answer = stringAdd(answer,stringBuilder.toString());
        }
        return answer;
    }

    /**
     * 大整数加法
     * @param str1
     * @param str2
     * @return
     */
    public String stringAdd(String str1, String str2){
        int num1Length = str1.length();
        int num2Length = str2.length();
        int maxLength = Math.max(num1Length,num2Length);
        // 少位的补 0 对齐
        if (num1Length < num2Length){
            for (int i = 0; i < num2Length-num1Length; i++) {
                str1 = '0' + str1;
            }
        }
        if (num1Length > num2Length){
            for (int i = 0; i < num1Length-num2Length; i++) {
                str2 = '0' + str2;
            }
        }
        StringBuilder stringBuilder = new StringBuilder();
        int jinwei = 0;
        for (int j = maxLength - 1;j >= 0 ;j--){
            int num1 = str1.charAt(j) - '0';
            int num2 = str2.charAt(j) - '0';
            int ans = num1 + num2 + jinwei;
            jinwei = ans / 10;
            stringBuilder.append(ans % 10);
        }
        // 有进位
        if (jinwei > 0){
            stringBuilder.append(jinwei);
        }
        return stringBuilder.reverse().toString();
    }
}

总结

其实就是考察移位运算的熟练程度,穿插了字符串加法的实现。

LeetCode 字符串加法

上一篇:字符串相加


下一篇:[PTA]7-12 两个数的简单计算器