字符串运算

实现字符串的加，乘法

一. 加法利用双指针，和人工的竖式运算相同
二. 乘法有两个版本：

1. 版本一为竖式运算普通版
2. 版本二是优化版的竖式运算。
   该算法是通过两数相乘时，乘数某位与被乘数某位相乘，与产生结果的位置的规律来完成。具体规律如下：
   • 乘数 num1 位数为 M，被乘数 num2 位数为 N， num1 x num2 结果 ans 最大总位数为 M+N，最小位数为 M+N-1
   • num[i] x num[j] 的结果 temp (为两位数，“0x"或者"xy”),其第一位位于 ans[i+j]，第二位位于 ans[i+j+1]

public static String addStrings(String num1, String num2){
    StringBuilder sb = new StringBuilder("");
    int i = num1.length()-1, j = num2.length()-1;
    int carry = 0;
    while(i >= 0 || j >= 0){
        int n1 = i >= 0 ? num1.charAt(i) - '0' : 0;
        int n2 = j >= 0 ? num2.charAt(j) - '0' : 0;
        int temp = n1 + n2 + carry;
        carry = temp / 10;
        sb.append(temp % 10);
        i--;j--;
    }
    if(carry==1) sb.append(1);
    return sb.reverse().toString();
}

public static String multiply(String num1, String num2) {
    if (num1.equals("0") || num2.equals("0"))   return "0";
    String ans = "0";
    for (int i = num2.length() - 1; i >= 0; i--){
        int carry = 0;
        int n2 = num2.charAt(i) - '0';
        StringBuilder sb = new StringBuilder("");

        for (int j = 0; j < num2.length()-i-1;j++)//补零
            sb.append("0");

        for (int k = num1.length() - 1; k >= 0; k--){//计算 n2*num1
            int n1 = num1.charAt(k) - '0';
            int temp = n1 * n2 + carry;
            sb.append(temp%10);
            carry = temp/10;
        }
        if(carry > 0) sb.append(carry);
        ans = addStrings(ans, sb.reverse().toString());
    }
    return ans;
}

public static String multiplyPlus(String num1, String num2){
    if (num1.equals("0") || num2.equals("0"))   return "0";

    int[] ans = new int[num1.length() + num2.length()];
    for (int i = num1.length() - 1; i >= 0; i--)
        for (int j = num2.length() - 1; j >= 0; j--){
            int n1 = num1.charAt(i) - '0';
            int n2 = num2.charAt(j) - '0';
            if(n1 == 0 || n2 ==0) continue;
            int temp = n1 * n2 + ans[i+j+1];
            ans[i+j+1] = temp % 10;
            ans[i+j] += temp / 10;
        }

    StringBuilder result = new StringBuilder();
    for (int i = 0; i < ans.length; i++) {
        //两个数相乘，位数是n+m(全9)或者n+m-1(只有一个1)，因此只有i=0的时候，才有可能抛弃一位0
        if (i == 0 && ans[i] == 0) continue;
        result.append(ans[i]);
    }
    return result.toString();
}