字符串算法题 - 字符串相加

字符串相加

415. 字符串相加 - 力扣（LeetCode） 刷题时间:

• 25/12/26

我的解法(没有解出来,且存在错误)

▼
java
复制代码
class Solution {
    public String addStrings(String num1, String num2) {
        int length1 = num1.length();
        int length2 = num2.length();
        if (length1 > length2) {
            String temp = num1;
            num1 = num2;
            num2 = temp;
        }

        // 获取char数组(逆序)
        char[] chars1 = toChars(num1);
        char[] chars2 = toChars(num2);

        // 两数组逐个相加, 结果保存到新char数组中, 注意进位
        char[] result = new char[length2 + 1];
        int up = 0;
        int i = 0;

        while (i < length1) {
            int a = chars1[i] - '0';
            int b = chars2[i] - '0';
            int sum = a + b + up;
            if (sum >= 10) {
                result[i] = '0' + (sum - 10);
                up = 1;
            } else {
                result[i] = '0' + sum;
            }
            i++;
            up = 0;
        }

        while (i < length2) {
            int b = chars2[i] - '0';
            int sum = b + up;
            if (sum >= 10) {
                result[i] = '0' + (sum - 10);
                up = 1;
            } else {
                result[i] = '0' + sum;
            }
            i++;
            up = 0;
        }

        // 将新char数组转为字符串
        if(result[result.length() - 1] == '0'){

        }

        // 返回结果

    }

    public char[] toChars(String str) {
        int length = str.length();
        char[] chars = new chars[length];
        int k = 0;

        // 访问字符串字符(逆序)
        for (int i = length - 1; i >= 0; i--) {
            // 插入char数组
            chars[k++] = str.charAt(i);
        }

        // 返回
        return chars;
    }
}

存在的bug

1. 变量交换的问题

2. up(进位)的处理问题

- 应该把up = 0;放在int sum = a + b + up;之后, if判断再进行赋值

3. 结果数组的处理问题

题解

1. 解法一(根据我的思路,修正而成)
   • 使用char[]数组存储结果result

▼
java
复制代码
class Solution {
    public String addStrings(String num1, String num2) {
        int i = num1.length() - 1;
        int j = num2.length() - 1;
        int carry = 0;

        // 结果最多比加数多一位
        char[] result = new char[Math.max(i, j) + 2];
        // 从后往前 相加求和
        int k = result.length - 1;

        while (i >= 0 || j >= 0 || carry > 0) {
            int a = (i >= 0) ? (num1.charAt(i--) - '0') : 0;
            int b = (j >= 0) ? (num2.charAt(j--) - '0') : 0;

            int sum = a + b + carry;
            carry = sum / 10;

            result[k--] = (char) ('0' + (sum % 10));
        }

		//char数组元素默认为'\u0000', 而不是'0'
        int start = (result[0] == '\u0000') ? 1 : 0;  
        return new String(result, start, result.length - start);
    }
}

• 注意点:
  • '\u0000' 是char的默认值，ASCII值为0，对应空字符
  • 在打印时显示为空，不是可见的'0'字符

2. 解法二(与解法一类似, 不过使用StringBuilder代替char[]数组)

▼
java
复制代码
class Solution {
    public String addStrings(String num1, String num2) {
        StringBuilder result = new StringBuilder();
        int i = num1.length() - 1;
        int j = num2.length() - 1;
        int carry = 0;

        while (i >= 0 || j >= 0 || carry > 0) {
            int a = (i >= 0) ? (num1.charAt(i--) - '0') : 0;
            int b = (j >= 0) ? (num2.charAt(j--) - '0') : 0;

            int sum = a + b + carry;
            carry = sum / 10;

            result.append(sum % 10);
        }

        return result.reverse().toString();
    }
}

思路:

• 使用两个指针(索引)指向两个字符串的末尾, 因为两数相加需要从后往前
  • 使用一个字符数组存储结果(char[] result), result的位数最多为(比两个字符串多一位)
  • 设置进位标志carry, 和结果数组的指针索引k
  • while(还有数字要处理 或 还有进位){
    • 当前位的数字(没有则设为0)
    • 计算和: a + b + carry
    • 更新结果: 当前位 = sum % 10; carry = sum / 10;
  • }
  • 三个指针都需要移动
  • 值得注意的是, 还需要判断result的第一位是否存在进位, 如果不存在, 那么就是'\u0000', 这是字符数组元素的默认值, 不是'0'.
  • 输出结果, new String(result,start,result.length() - start)
    • new String(字符数组,开始索引, 截取个数)
• 第二种思路, 与第一种思路是差不多的, 差别只是使用了StringBuilder来存储结果.
  • 使用char数组有以下缺点:
    • 1. 需要设置数组的长度, 由题意需要设置一个"大一位"的数组, 就会导致在最后处理结果时, 需要考虑是否有进位,
    • 2. 转换为字符串不方便, 需要截取
  • 使用StringBuilder有以下优点:
    • 1. 不需要设置长度, 使用result.append()即可在尾部添加字符(后续进行字符串的反转即可)
    • 2. 反转和转换为String有现成函数可以调用, 很方便.
      • result.reverse(); result.toString();

算法思想:

1. 大数相加的通用模式
   • 通过while循环判断是否存在数字需要处理,及是否还有进位
   • 取数字进行相加,不存在即设置为0, 正常相加
   • 计算两数及进位的和, 更新结果及进位
   • 最后输出结果(涉及反转,转为String等操作)
2. 字符与数字的转换
   • `int num = c - '0';
   • char c = (char)('0' + num);
3. 加法 - 从后往前
   • 加法从最低位(右边)开始
4. StringBuilder
   • 一个很好用的字符串类
   • String不可变, 它可变, 动态扩展, 效率高
   • 具备便捷的操作字符串的函数(append, reverse, toString)