【LeetCode每日一题】——415.字符串相加

一【题目类别】

• 字符串

二【题目难度】

• 简单

三【题目编号】

• 415.字符串相加

四【题目描述】

• 给定两个字符串形式的非负整数 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$ 都不包含任何前导零

七【解题思路】

• 我们只需要模拟十进制加法的过程即可
• 从后向前遍历两个字符串
• 进行加法运算，并计算得到进位
• 然后根据进位继续向下运算，得到每一对值的计算结果
• 如果某一个加数计算完毕，对其补零继续运算，直到运算结束
• 注意最后一次计算可能会有进位，所以需要特殊判断
• 具体细节可以参考下面的代码
• 最后返回结果即可

八【时空频度】

• 时间复杂度：$O(max(m,n))$，$m$和$n$分别为字符串1和字符串2的长度
• 空间复杂度：$O(1)$

九【代码实现】

1. Java语言版

class Solution {public String addStrings(String num1, String num2) {// 分别定义两个字符串的索引指向末尾int i = num1.length() - 1;int j = num2.length() - 1;// 保持进位int add = 0;// 保存结果StringBuilder res = new StringBuilder();// 字符串相加while (i >= 0 || j >= 0) {// 获取两个加数int temp1 = (i >= 0) ? num1.charAt(i) - '0' : 0;int temp2 = (j >= 0) ? num2.charAt(j) - '0' : 0;// 根据进位计算当前位的和int temp = temp1 + temp2 + add;// 计算进位add = temp / 10;// 计算当前位的求和值res.insert(0, temp % 10);// 向前继续求和i--;j--;}// 返回结果（注意：最后一次计算可能会有进位，需要特殊判断）if (add != 0) {res.insert(0, add);}return res.toString();}
}

2. Python语言版

class Solution:def addStrings(self, num1: str, num2: str) -> str:# 分别定义两个字符串的索引指向末尾i = len(num1) - 1j = len(num2) - 1# 保持进位add = 0# 保存结果res = ""# 字符串相加while i >= 0 or j >= 0:# 获取两个加数temp1 = int(num1[i]) if i >= 0 else 0temp2 = int(num2[j]) if j >= 0 else 0# 根据进位计算当前位的和temp = temp1 + temp2 + add# 计算进位add = temp // 10# 计算当前位的求和值res = str(temp % 10) + res# 向前继续求和i -= 1j -= 1# 返回结果（注意：最后一次计算可能会有进位，需要特殊判断）return "1" + res if add else res

3. C++语言版

class Solution {
public:string addStrings(string num1, string num2) {// 分别定义两个字符串的索引指向末尾int i = num1.length() - 1;int j = num2.length() - 1;// 保持进位int add = 0;// 保存结果string res = "";// 字符串相加while (i >= 0 || j >= 0) {// 获取两个加数int temp1 = (i >= 0) ? num1[i] - '0' : 0;int temp2 = (j >= 0) ? num2[j] - '0' : 0;// 根据进位计算当前位的和int temp = temp1 + temp2 + add;// 计算进位add = temp / 10;// 计算当前位的求和值res = char((temp % 10) + '0') + res;// 向前继续求和i--;j--;}// 返回结果（注意：最后一次计算可能会有进位，需要特殊判断）if (add) {return '1' + res;}return res;}
};

十【提交结果】

1. Java语言版
   

2. Python语言版
   

3. C++语言版