2022-06-14.md

每日一题 - 字符串处理

信息卡片

• 时间：2022-06-14
• 题目链接：https://leetcode.com/problems/add-strings/
• tag：数学 字符串 模拟

题目描述

给定两个字符串形式的非负整数 num1 和 num2 ，计算它们的和并同样以字符串形式返回。

你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。

示例1：

输入：num1 = "11", num2 = "123"
输出："134"

示例2：

输入：num1 = "456", num2 = "77"
输出："533"

示例3：

输入：num1 = "0", num2 = "0"
输出："0"

提示：

• 1 <= num1.length, num2.length <= 10^4
• num1 和 num2 都只包含数字 0-9
• num1 和 num2 都不包含任何前导零

进阶：

思路分析

1. 拆分字符串进行位相加
   • 不能整体转换为整数形式，但是可以每一位单独转换
   • 通过 ASCII 码转换
     • 字符 0：十进制 48
     • 字符 6：十进制 54
     • '6' - '0' = 6
2. 进位 单独存储

参考答案

1. 模拟竖式加法 $O(max(len1​,len2​))$

空间复杂度：$O(1)$

function addStrings(num1, num2) {
  let result = []
  // 记录进位
  let carry = 0
  // num1, num2, carry 都为 0 则结束
  for (let i = num1.length - 1, j = num2.length - 1; i >= 0 || j >= 0 || carry === 1; i--, j--) {
    // < 0 则用 0 
    const x = i < 0 ? 0 : num1.charAt(i) - '0'
    const y = j < 0 ? 0 : num2.charAt(j) - '0'
    const z = x + y + carry
    result.push(z % 10)
    carry = parseInt(z / 10)
  }
  return result.reverse().join('')
}