文章

字符串相加问题详解：从简单到复杂的全面分析

发表于 更新于
作者 smallbei 17 分钟阅读

一、基本概念

1. 什么是字符串相加？

字符串相加是一类特殊的算法问题,主要处理以字符串形式表示的数字的加法运算。这类问题的特点是:

  • 输入是以字符串形式表示的数字
  • 数字可能非常大,超出常规整数类型的范围
  • 需要模拟人工加法的过程
  • 结果同样以字符串形式返回

例如:

1
2

"123" + "456" = "579"
"1234567890" + "9876543210" = "11111111100"

2. 为什么需要字符串相加？

  1. 处理大数
    • 超出整数范围的数字计算
    • 避免数值溢出问题
    • 保持精确计算
  2. 实际应用场景
    • 金融计算
    • 科学计算
    • 大数据处理
  3. 算法思维训练
    • 培养模拟能力
    • 提高字符串处理能力
    • 锻炼进位处理思维

3. 基本解题思路

  1. 对齐处理
    • 从个位开始对齐
    • 处理不等长字符串
    • 补零对齐
  2. 逐位相加
    • 按位计算和
    • 处理进位
    • 保存结果
  3. 结果处理
    • 处理最高位进位
    • 去除前导零
    • 返回最终字符串

二、基础实现方案

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

func addStrings(_ num1: String, _ num2: String) -> String {
    // 处理边界情况
    guard !num1.isEmpty && !num2.isEmpty else {
        return num1.isEmpty ? num2 : num1
    }
    
    var chars1 = Array(num1)
    var chars2 = Array(num2)
    var result = ""
    var carry = 0
    
    // 从后向前遍历
    var i = chars1.count - 1
    var j = chars2.count - 1
    
    while i >= 0 || j >= 0 || carry > 0 {
        let digit1 = i >= 0 ? Int(String(chars1[i]))! : 0
        let digit2 = j >= 0 ? Int(String(chars2[j]))! : 0
        
        let sum = digit1 + digit2 + carry
        carry = sum / 10
        result = String(sum % 10) + result
        
        i -= 1
        j -= 1
    }
    
    return result
}

三、进阶问题

1. 数字字符串加一

LeetCode 66. 加一

问题描述：给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

示例：

1
2
3
4
5
6
7

输入: [1,2,3]
输出: [1,2,4]
解释: 123 + 1 = 124

输入: [9,9,9]
输出: [1,0,0,0]
解释: 999 + 1 = 1000

1
2
3
4
5
6
7
8
9
10
11
12
13
14

func plusOne(_ digits: [Int]) -> [Int] {
    var result = digits
    
    for i in (0..<result.count).reversed() {
        if result[i] < 9 {
            result[i] += 1
            return result
        }
        result[i] = 0
    }
    
    result.insert(1, at: 0)
    return result
}

2. 二进制字符串相加

LeetCode 67. 二进制求和

给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。

示例1：

1
2
3
4
5
6
7

输入: a = "11", b = "1"
输出: "100"
解释：
  11
   1
---
 100

示例2：

1
2
3
4
5
6
7

输入: a = "1010", b = "1011"
输出: "10101"
解释：
  1010
  1011
------
 10101

关键点：

  • 二进制加法规则：1+1=10
  • 需要处理进位
  • 结果可能比输入字符串更长

与十进制加法的区别：

  1. 进位规则不同（逢2进1，而不是逢10进1）
  2. 每位只能是0或1
  3. 计算更简单但容易出错
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

func addBinary(_ a: String, _ b: String) -> String {
    // 特殊情况处理
    if a == "0" { return b }
    if b == "0" { return a }
    
    var result = ""
    var carry = 0
    
    let chars1 = Array(a)
    let chars2 = Array(b)
    var i = chars1.count - 1
    var j = chars2.count - 1
    
    // 从后向前遍历
    while i >= 0 || j >= 0 || carry > 0 {
        let bit1 = i >= 0 ? Int(String(chars1[i]))! : 0
        let bit2 = j >= 0 ? Int(String(chars2[j]))! : 0
        
        // 二进制加法
        let sum = bit1 + bit2 + carry
        carry = sum / 2
        result = String(sum % 2) + result
        
        i -= 1
        j -= 1
    }
    
    return result
}

// 优化版本：使用位运算 -- 可以忽略不计 不好理解
func addBinaryOptimized(_ a: String, _ b: String) -> String {
    // 将二进制字符串转换为字符数组
    let chars1 = Array(a)
    let chars2 = Array(b)
    let n1 = chars1.count
    let n2 = chars2.count
    let maxLen = max(n1, n2)
    
    // 使用数组存储每一位的结果，避免字符串拼接
    var result = Array(repeating: "0", count: maxLen + 1)
    var carry = 0
    
    // 从低位到高位处理
    for i in 0..<maxLen {
        // 使用位运算获取当前位
        let p1 = n1 - 1 - i
        let p2 = n2 - 1 - i
        
        // 使用位运算计算当前位的值
        let bit1 = p1 >= 0 ? chars1[p1] == "1" ? 1 : 0 : 0
        let bit2 = p2 >= 0 ? chars2[p2] == "1" ? 1 : 0 : 0
        
        // 使用异或运算计算当前位
        let sum = bit1 ^ bit2 ^ carry
        
        // 使用与运算计算进位
        // carry = 1 当且仅当至少有两个1
        carry = (bit1 & bit2) | (bit1 & carry) | (bit2 & carry)
        
        // 从低位开始填充结果
        result[maxLen - i] = String(sum)
    }
    
    // 处理最高位的进位
    if carry > 0 {
        result[0] = "1"
        return result.joined()
    }
    
    // 去除前导零
    return result[1...].joined()
}

// 添加测试用例和解释
/*
位运算优化说明：
1. 异或运算(^)：计算不带进位的和
    0 ^ 0 = 0
    0 ^ 1 = 1
    1 ^ 0 = 1
    1 ^ 1 = 0

2. 与运算(&)：计算进位
    当有两个或以上的1时产生进位
    可以用 (a & b) | (a & c) | (b & c) 判断

3. 性能优化：
    - 避免字符串拼接操作
    - 使用位运算代替算术运算
    - 预分配结果数组空间

测试用例：
a = "10100000100100110110010000010101111011011001101110111111111101000000101111001110001111100001101"
b = "110101001011101110001111100110001010100001101011101010000011011011001011101111001100000011011110011"

解释：
1. 预分配长度为max(len(a), len(b)) + 1的结果数组
2. 从低位到高位，使用位运算处理每一位
3. 使用异或运算计算当前位的值
4. 使用与运算计算进位
*/

3. 复数字符串运算

LeetCode 537. 复数乘法

给定两个表示复数的字符串，返回表示它们乘积的字符串。注：复数的格式为”a+bi”，其中a和b都是实数。

示例1：

1
2
3
4

输入: "1+1i", "1+1i"
输出: "0+2i"
解释: 
(1 + i) * (1 + i) = 1 - 1 + 2i = 2i

示例2：

1
2
3
4

输入: "1+-1i", "1+-1i"
输出: "2+-2i"
解释:
(1 - i) * (1 - i) = 1 + 1 - 2i = 2 - 2i

关键点：

  • 需要分别处理实部和虚部
  • 字符串解析要处理负数
  • 结果格式需要统一

这三个问题的共同点：

  1. 都需要处理字符串形式的数字
  2. 都涉及进位处理
  3. 都需要考虑特殊情况

主要区别：

  1. 进制不同（十进制、二进制）
  2. 数据类型不同（整数、复数）
  3. 运算规则不同（加法、乘法）

易错点总结：

  1. 进位处理不当
  2. 特殊情况未考虑（0、负数、空串）
  3. 结果格式不统一
  4. 字符串解析错误

优化方向：

  1. 使用数组预处理提高效率
  2. 原地修改减少空间使用
  3. 特殊情况早判断避免无效计算
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

func complexNumberMultiply(_ num1: String, _ num2: String) -> String {
    // 解析复数字符串
    func parseComplex(_ s: String) -> (Int, Int) {
        // 处理带负号的情况
        let parts = s.split(separator: "+")
        var real: Int
        var imag: Int
        
        if parts.count == 1 {
            // 只有一部分，可能是纯实数或纯虚数
            let part = String(parts[0])
            if part.hasSuffix("i") {
                // 纯虚数
                imag = Int(part.dropLast()) ?? 0
                real = 0
            } else {
                // 纯实数
                real = Int(part) ?? 0
                imag = 0
            }
        } else {
            // 有实部和虚部
            real = Int(parts[0]) ?? 0
            imag = Int(String(parts[1].dropLast())) ?? 0
        }
        return (real, imag)
    }
    
    // 解析两个复数
    let (real1, imag1) = parseComplex(num1)
    let (real2, imag2) = parseComplex(num2)
    
    // 计算复数乘法
    // (a + bi)(c + di) = (ac - bd) + (ad + bc)i
    let realResult = real1 * real2 - imag1 * imag2
    let imagResult = real1 * imag2 + real2 * imag1
    
    // 构造结果字符串
    return "\(realResult)+\(imagResult)i"
}

// 优化版本：支持更复杂的格式和边界情况
func complexNumberMultiplyOptimized(_ num1: String, _ num2: String) -> String {
    // 增强的复数解析函数
    func parseComplexEnhanced(_ s: String) -> (Int, Int) {
        var str = s.replacingOccurrences(of: " ", with: "")
        
        // 分割实部和虚部
        let components = str.split(separator: "+", maxSplits: 1)
        
        // 处理实部
        let real = Int(components[0]) ?? 0
        
        // 处理虚部（去掉'i'并转换为整数）
        var imag = 0
        if components.count > 1 {
            let imagStr = String(components[1].dropLast()) // 去掉'i'
            imag = Int(imagStr) ?? 0
        }
        
        return (real, imag)
    }
    
    let (real1, imag1) = parseComplexEnhanced(num1)
    let (real2, imag2) = parseComplexEnhanced(num2)
    
    // 复数乘法
    let realResult = real1 * real2 - imag1 * imag2
    let imagResult = real1 * imag2 + real2 * imag1
    
    // 直接返回标准格式
    return "\(realResult)+\(imagResult)i"
}

四、优化技巧

1. 空间优化

  • 使用原地修改而不是创建新字符串
  • 预分配合适大小的数组
  • 复用已有空间

2. 时间优化

  • 使用位运算代替除法和取模
  • 避免不必要的字符串转换
  • 特殊情况提前处理

3. 代码优化

  • 提取公共函数
  • 使用更清晰的变量命名
  • 添加适当的注释

五、常见错误和解决方案

  1. 进位处理错误
    1
2
3
4

    // 错误示例
let sum = digit1 + digit2 // 漏掉了carry
// 正确处理
let sum = digit1 + digit2 + carry
  2. 边界情况处理不当
    1
2
3
4

    // 错误示例
let digit = Int(String(chars[i]))! // 可能崩溃
// 正确处理
let digit = i >= 0 ? Int(String(chars[i])) ?? 0 : 0
  3. 格式化输出问题
    1
2
3
4
5

    // 错误示例
return "\(real)+\(imag)i" // 没有处理负数情况
// 正确处理
let sign = imag >= 0 ? "+" : ""
return "\(real)\(sign)\(imag)i"

六、性能分析

1. 时间复杂度

  • 基本实现：O(max(n,m))，n和m为输入字符串的长度
  • 多字符串相加：O(n*k)，k为字符串数量
  • 优化版本：O(max(n,m))，但常数更小

2. 空间复杂度

  • 基本实现：O(max(n,m))
  • 原地修改：O(1)
  • 查表优化：O(1)额外空间，但有固定大小的表

七、实战技巧

1. 编写字符串相加代码的步骤

  1. 处理特殊情况（空字符串、零等）
  2. 对齐字符串
  3. 实现逐位相加
  4. 处理进位
  5. 优化性能

2. 调试技巧

  1. 使用小规模测试用例
  2. 验证边界情况
  3. 检查进位处理
  4. 注意前导零

3. 代码模板

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

// 通用字符串相加模板
func stringAddition(_ num1: String, _ num2: String) -> String {
    // 1. 参数验证
    guard !num1.isEmpty && !num2.isEmpty else {
        return num1.isEmpty ? num2 : num1
    }
    
    // 2. 初始化变量
    var result = ""
    var carry = 0
    var i = num1.count - 1
    var j = num2.count - 1
    let chars1 = Array(num1)
    let chars2 = Array(num2)
    
    // 3. 主循环
    while i >= 0 || j >= 0 || carry > 0 {
        // 获取当前位
        let digit1 = i >= 0 ? Int(String(chars1[i]))! : 0
        let digit2 = j >= 0 ? Int(String(chars2[j]))! : 0
        
        // 计算和与进位
        let sum = digit1 + digit2 + carry
        carry = sum / 10
        result = String(sum % 10) + result
        
        // 移动指针
        i -= 1
        j -= 1
    }
    
    // 4. 返回结果
    return result
}

八、总结

1. 适用场景

  • 大数计算
  • 精确计算
  • 进制转换
  • 复数运算

2. 优缺点

优点：

  • 可处理任意大的数字
  • 精确计算无误差
  • 实现简单直观

缺点：

  • 计算速度较慢
  • 需要额外空间
  • 代码较为冗长

3. 实践建议

  1. 注意边界条件
  2. 合理使用优化技巧
  3. 重视代码可读性
  4. 做好错误处理

九、练习题推荐

  1. LeetCode相关题目：
    • #415 字符串相加
    • #67 二进制求和
    • #43 字符串相乘
    • #989 数组形式的整数加法
    • #2 两数相加（链表版本）
  2. 进阶练习：
    • #66 加一
    • #369 给单链表加一
    • #445 两数相加 II
    • #537 复数乘法
算法 字符串 数学 LeetCode
本文由作者按照 CC BY 4.0 进行授权