字符串四则运算

## 加法

> 题目来源：[415. 字符串相加](https://leetcode-cn.com/problems/add-strings)。

### 题目

给定两个字符串形式的非负整数 `num1` 和 `num2` ，计算它们的和。

**提示：**

1. `num1` 和 `num2` 的长度都小于 5100。
2. `num1` 和 `num2` 都只包含数字 0-9。
3. `num1` 和 `num2` 都不包含任何前导零。
4. 你不能使用任何內建 `BigInteger` 库， 也不能直接将输入的字符串转换为整数形式。

### 问题分析

1. 如果两个字符串的长度不同，则将位数较短的字符串补零，使其和较长的字符串长度相同。
2. 将两个字符串各位进行相加：
   1. 两个字符串当前数字分别是 $a$、$b$，进位值 $plus$ 初始为 0。
   2. 将 $a$、$b$、$plus$ 相加得 $cur$，同时令 $plus = cur / 10$，并将 $cur \% 10$ 添加到 $res$ 中。
3. 如果最后 $plus$ 大于 0，说明最后一位又有进位，将 $plus$ 添加到最终结果 $res$ 中。
4. 前面得到的结果 $res$ 是反的，将其反转一下返回即可。

### 参考代码

```java
/**
* 415. 字符串相加（模拟竖式算法）
* @param s string 字符串 表示第一个整数
* @param t string 字符串 表示第二个整数
* @return string 字符串
*/
public String solve (String s, String t) {
   String temp = (s.length() < t.length() ? s : t);
   String temp2 = (s.length() >= t.length() ? s : t);
   StringBuffer sb = new StringBuffer(temp);
   sb = sb.reverse();
   
   //   将较短的字符串前面补零，使其和长的字符串对齐，便于后面计算
   for (int i = 0; i < Math.abs(s.length() - t.length()); i++) {
       sb.append("0");
   }
   
   temp = sb.reverse().toString();  //  补齐后的字符串
   sb = new StringBuffer();
   int plus = 0;    //  进位
   for (int i = temp.length() - 1; i >= 0; i--) {
       int cur = (temp.charAt(i) - '0') + (temp2.charAt(i) - '0') + plus;
       plus = cur / 10;
       sb.append(cur % 10);
   }
   
   if (plus > 0) {sb.append(plus);} //  最后一位如果进位，则将其添加到最后的结果中
   
   return sb.reverse().toString();
}
```

## 乘法

> 题目来源：[43. 字符串相乘](https://leetcode-cn.com/problems/multiply-strings)。

### 题目

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

**示例 1:**

```txt
输入: num1 = "2", num2 = "3"
输出: "6"
```

**示例 2:**

```txt
输入: num1 = "123", num2 = "456"
输出: "56088"
```

**说明：**

1. num1 和 num2 的长度小于 110。
2. num1 和 num2 只包含数字 0-9。
3. num1 和 num2 均不以零开头，除非是数字 0 本身。
4. 不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

### 问题分析

1. 该算法是**通过两数相乘时**，**乘数某位与被乘数某位相乘**，**与产生结果的位置的规律来完成**，具体规律如下：
   1. **乘数 $num_1$ 位数为 $M$**，**被乘数 $num_2$ 位数为 $N$**，$num_1 \times num_2$**结果 $res$ 最大总位数为 $M + N$**。
   2. $num_1[i] \times num_2[j]$**的结果为 $tmp$**（位数为两位，形如 `0x`、`xy`），其中**第一位位于 $res[i + j]$**，**第二位位于 $res[i + j + 1]$**。![](https://notebook.ricear.com/media/202111/2021-11-11_2206230.7681314149420733.png)

### 参考代码

```java
/**
 * 43. 字符串相乘
 * @param num1  字符串 1
 * @param num2  字符串 2
 * @return  两个字符串的乘积
 */
public String multiply(String num1, String num2) {
    if (num1.equals("0") || num2.equals("0")) {return "0";}

//  两个长度分为为 m、n 的字符串相加后得到的结果的最大长度为 m + n
    int[] res = new int[num1.length() + num2.length()];
    for (int i = num1.length() - 1; i >= 0; i--) {
        int m = num1.charAt(i) - '0';
        for (int j = num2.length() - 1; j >= 0; j--) {
            int n = num2.charAt(j) - '0';
            int sum = res[i + j + 1] + m * n;
            //  num1.charAt(i) * num2.charAt(j) 的到的结果（以两位数来算，形如"0x"、"xy"）中，十位数为 res[i + j]，个位数为 res[i + j + 1]
            res[i + j] += sum / 10;
            res[i + j + 1] = sum % 10;
        }
    }

StringBuilder result = new StringBuilder();
    for (int i = 0; i < res.length; i++) {
        //  如果第一位数为 0，则过滤掉
        if (i == 0 && res[i] == 0) {continue;}
        result.append(res[i]);
    }

//  返回最后结果
    return result.toString();
}
```

## 参考文献

1. [415. 字符串相加](https://leetcode-cn.com/problems/add-strings)。
2. [字符串相加 （双指针，清晰图解）](https://leetcode-cn.com/problems/add-strings/solution/add-strings-shuang-zhi-zhen-fa-by-jyd)。
3. [43. 字符串相乘](https://leetcode-cn.com/problems/multiply-strings)。
4. [优化版竖式(打败 99.4%)](https://leetcode-cn.com/problems/multiply-strings/solution/you-hua-ban-shu-shi-da-bai-994-by-breezean)。