Multiply Strings大整数乘法

［抄题］：

以字符串的形式给定两个非负整数 num1 和 num2，返回 num1 和 num2 的乘积。

[暴力解法]：

时间分析：

空间分析：

［思维问题］：

还要找到结果中第一位不等于0的数再添加，没想到

［一句话思路］：

套公式, 没有carry进位了，全都是对ans直接进行操作：

ans[i + j] += a [i] * b[j]

全部相乘之后再统一进位

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

Multiply Strings大整数乘法

［一刷］：

长度用l1 l2来表示，比较简单。二者合并后的新数组要为0新添加一位，变成num[l1 + l2 + 1]
while循环可以加2个条件，括号里不止有一个东西，从而控制几个条件 while (i >= 1 && ans[i] == 0)
结果添加的时候，index也可以变，从而不用for就一直往后添加 result += ans[i--]

［二刷］：

［三刷］：

［四刷］：

［五刷］：

[五分钟肉眼debug的结果]：

［总结］：

没有变量carry，但是有carry进位的过程：直接对ans[]进行操作

［复杂度］：Time complexity: O(n) Space complexity: O(n)

［英文数据结构或算法，为什么不用别的数据结构或算法］：

［其他解法］：

［Follow Up］：

［LC给出的题目变变变］：

[代码风格] ：

public class Solution {

    /**

     * @param num1: a non-negative integers

     * @param num2: a non-negative integers

     * @return: return product of num1 and num2

     */

    public String multiply(String num1, String num2) {

        //mutiply

        int l1 = num1.length();

        int l2 = num2.length();

        int[] ans = new int[l1 + l2 + 1];//add new

        for (int i = 0; i < l1; i++) {

            for (int j = 0; j < l2; j++) {

                ans[i + j] += (num1.charAt(l1 - 1 - i) - '0') *

                (num2.charAt(l2 - 1 - j) - '0');

            }

        }

        //carry process

        for (int i = 0; i < l1 + l2; i++) {

            ans[i + 1] += ans[i] / 10;

            ans[i] = ans[i] % 10;//

        }

        //find first position

        int i = l1 + l2;

        while (i >= 1 && ans[i] == 0) {//

            i--;

        }

        //add to ans

        String result = "";

        while (i >= 0) {

            result += ans[i--]; //i should move

        }

        return result;

    }

}

秒客网

Multiply Strings大整数乘法

相关文章