[LeetCode] 43. 字符串相乘（java实现）

1. 题目2. 读题（需要重点注意的东西）3. 解法4. 可能有帮助的前置习题5. 所用到的数据结构与算法思想6. 总结

思路1（模拟题）：
高精度乘法
A[i] * B[j] = C[i + j]

---------------------------------------------------解法---------------------------------------------------：

class Solution {
    // 高精度乘法
    public String multiply(String num1, String num2) {
        int n = num1.length(),m = num2.length();
        int[] A = new int[n],B = new int[m],C = new int[m + n];
        // 低位放在数组低位，高位放在数组高位
        for(int i = n - 1;i >= 0;i--) A[n - i - 1] = num1.charAt(i) - '0';
        for(int i = m - 1;i >= 0;i--) B[m - i - 1] = num2.charAt(i) - '0';
        // 模拟乘法
        for(int i = 0;i < n;i++)
            for(int j = 0;j < m;j++)
                C[i + j] += A[i] * B[j];

        // 将C的每一个大于等于10的数进位
        for(int i = 0,t = 0;i < C.length;i++){
            t += C[i]; // 进位加当前位上的数
            C[i] = t % 10; // 进位后的数
            t /= 10; // 进位
        }

        // 将高位的0去掉
        int k = C.length - 1;
        while(k > 0 && C[k] == 0) k--;

        // 转为String
        StringBuilder res = new StringBuilder();
        while (k >= 0) res.append(String.valueOf(C[k--]));

        return res.toString();
    }
}

可能存在的问题：

[AcWing]791. 高精度加法（C++实现）模板题 5. 所用到的数据结构与算法思想

Java数据结构—String（字符串及其常用操作）含StringBuffer 和 StringBuilder 类 6. 总结