字符串

发表于 分类于 ， 本文字数： 734 阅读时长 ≈ 3 分钟 阅读次数：

相似解法题目多元组

  • 模拟：<BM86 大数加法，BM11 链表相加(二)>

BM86 大数相加

描述

以字符串的形式读入两个数字，编写一个函数计算它们的和，以字符串形式返回。

例如，输入 "1", "99"，返回 "100"。

思路

模拟

大整数相加，可以按照整数相加的方式，从个位开始，逐渐向上累加。在字符串中就是从两个字符串的末尾开始相加。

F1：模拟法

步骤

做法与 BM11 链表相加（二）几乎一致。不同的地方，一个是字符串可以直接从后向前遍历；二是在于最后的进位需要在返回前进行判断，再决定是否给字符串添加进位'1'。

  1. 若是其中一个字符串为空，直接返回另一个，不用加了。
  2. 设置两个用于遍历各自字符串的下标 i，j 以及用于遍历辅助字符数组的下标 p，取最大的字符串长度作为辅助字符数组的长度，设置进位 carry = 0。
  3. 从后开始遍历两个字符串，直到两个下标都为 -1。每次取出非 -1 的下标的字符转换成数字，如果是 -1 就设置为 0，将两个转换好的数字与carry 相加，然后查看是否进位，将进位后的结果（对 10 取模）放入对应辅助字符数组内，并继续向前遍历。
  4. 遍历结束后，将辅助字符数组转换成字符串，如果存在进位，则直接在字符串前增加一个字符 '1'。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public static String solve(String s, String t) {
    // 1. 其中一个为空，返回另一个
    if (s.length() <= 0)
        return t;
    if (t.length() <= 0)
        return s;
    // 2. 设置辅助参数
    int carry = 0; // 设置进位
    int i = s.length() - 1; // s 下标
    int j = t.length() - 1; // t 下标
    char[] help = new char[Math.max(i, j) + 1]; // 取最大的字符串长度作为辅助字符数组的长度
    int p = help.length - 1; // 辅助数组下标
    // 3. 只要某个字符串还有字符
    while (i != -1 || j != -1) {
        // 下标不为 -1，取出字符并转换成数字，否则为 0。
        int a = i == -1 ? 0 : s.charAt(i) - '0';
        int b = j == -1 ? 0 : t.charAt(j) - '0';
        // 相加
        int sum = a + b + carry;
        // 获取进位
        carry = sum / 10;
        // 获取放入辅助数组的值，取模去掉十位
        sum %= 10;
        // 将数值转换成字符
        help[p] = (char)(sum + '0');
        p--;
        // 下标不为 -1，向前移动
        if (i != -1)
            i--;
        if (j != -1)
            j--;
    }
    // 4. 将辅助字符数组转换成字符串
    String output = String.valueOf(help);
    // 如果进位还存在，在字符串前增加一个字符 '1'
    if (carry == 1)
        output = '1' + output;
    return output;
}
时间复杂度

\(O(max(m,n))\)

其中 m 与 n 分别为两个字符串的长度。

空间复杂度

\(O(max(m,n))\)

其中 m 与 n 分别为两个字符串的长度，用于辅助字符数组。