题解 | #大数乘法#

解题思路 1

1. 使两个字符串分别用一个字符进行相乘并加上进位标志的值记录结果
2. 将记录结果添加到缓存中
   1. 如果缓存对应索引有字符进行相加并替换原来字符
   2. 如果缓存对应索引没有字符直接添加到缓存中
3. 如果有值大于 10，将多出部分赋值给进位标志里面进行后续相加
4. 如果某一个字符串相乘完还有进位标志，那么直至进位标志赋值为零才能结束当前循环

代码实现

public class Solution {
    public String solve (String s, String t) {
        if(s.equals("0")||t.equals("0"))return "0";
        StringBuffer t1 = new StringBuffer(t);
        StringBuffer s1 = new StringBuffer(s);
        t1 = t1.reverse();
        s1 = s1.reverse();
        StringBuffer temp = new StringBuffer();
        for(int i =0;i<s1.length();i++){
            int tag = 0;
            for(int j=0;j<t1.length();j++){
                int res = (s1.charAt(i)-48)*(t1.charAt(j)-48)+tag;
                if(temp.length()<=j+i)temp.append(res%10);
                else {
                    res += temp.charAt(j+i)-48;
                    temp.replace(j+i, j+i+1, ""+res%10);
                }
                tag = res/10;
            }
            int j = i;
            while(tag!=0){
                if(temp.length()<=t1.length()+j)temp.append(tag%10);
                else{
                    tag += temp.charAt(t.length()+j)-48;
                    temp.replace(t1.length()+j, t1.length()+j+1, ""+tag%10);
                }
                tag /= 10;
                j++;
            }
        }
        return temp.reverse().toString();
    }
}
// 运行时间：216ms	超过3.26% 用Java提交的代码
// 占用内存：15808KB	超过6.75% 用Java提交的代码

时间复杂度: $O(n^2)O(n^\{2\})$

空间复杂度: $O(n)O(n)$

out-place