LeetCode 字符串相乘

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

示例说明:请看LeetCode官网

解法一:数组遍历

  • 首先,如果num1和num2有为0的,直接返回空字符串。
  • 否则,声明一个list为temp用来记录每一行的乘积的结果;
  • 然后将这些行的结果累加起来;
  • 最后将累加的结果按倒序拼成字符串返回。
import java.util.ArrayList;
import java.util.List;

public class LeetCode_043 {
    public static String multiply(String num1, String num2) {
        if ((num1 == null || num1.length() == 0) || (num2 == null || num2.length() == 0)) {
            return "";
        }
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }
        /**
         * 如果num2的长度大于num1的长度将num1和num2的值交换
         */
        if (num2.length() > num1.length()) {
            String temp = num1;
            num1 = num2;
            num2 = temp;
        }
        /**
         * 记录每一行的乘积的结果
         */
        List<int[]> temp = new ArrayList<>();
        int count = 0;
        for (int i = num2.length() - 1; i >= 0; i--) {
            int c2Num = num2.charAt(i) - '0';
            int[] cur = new int[num1.length() + num2.length()];
            int index = 0;
            for (; index < count; index++) {
                cur[index] = 0;
            }
            int addOne = 0;
            for (int j = num1.length() - 1; j >= 0; j--) {
                int c1Num = num1.charAt(j) - '0';
                if (c2Num * c1Num + addOne > 9) {
                    cur[index++] = (c2Num * c1Num + addOne) % 10;
                    addOne = (c2Num * c1Num + addOne) / 10;
                } else {
                    cur[index++] = c2Num * c1Num + addOne;
                    addOne = 0;
                }
            }
            if (addOne > 0) {
                cur[index] = addOne;
            }
            temp.add(cur);
            count++;
        }

        int addOne = 0;
        List<Integer> result = new ArrayList<>();
        /**
         * 将每一行的乘积结果累加起来
         */
        for (int i = 0; i < num1.length() + num2.length(); i++) {
            int curNum = addOne;
            for (int[] ints : temp) {
                curNum += ints[i];
            }
            if (curNum > 9) {
                result.add(curNum % 10);
                addOne = curNum / 10;
            } else {
                result.add(curNum % 10);
                addOne = 0;
            }
        }

        String resultStr = "";
        int firstNoneZeroIndex = -1;
        /**
         * 找到第一个不为0的数字
         */
        for (int i = result.size() - 1; i >= 0; i--) {
            if (result.get(i) != 0) {
                firstNoneZeroIndex = i;
                break;
            }
        }
        /**
         * 将最后的结果拼成string并最后返回
         */
        for (int i = firstNoneZeroIndex; i >= 0; i--) {
            resultStr += String.valueOf(result.get(i));
        }
        return resultStr;
    }

    public static void main(String[] args) {
        // 测试用例,预计输出: 56088
        System.out.println(multiply("123", "456"));
    }
}

「点点赞赏,手留余香」

1

给作者打赏,鼓励TA抓紧创作!

微信微信 支付宝支付宝

还没有人赞赏,快来当第一个赞赏的人吧!

声明:本站所有资源及文章均来源于网络及用户分享或为本站原创,仅限用于学习和研究,任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。
码云笔记 » LeetCode 字符串相乘

发表评论

IT互联网行业相关广告投放 更专业 更精准

立即查看 联系我们