当前位置：首页 > article >正文

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

article 2024/12/24 12:21:51

文章目录

一【题目类别】
二【题目难度】
三【题目编号】
四【题目描述】
五【题目示例】
六【题目提示】
七【解题思路】
八【时空频度】
九【代码实现】
十【提交结果】

一【题目类别】

字符串

二【题目难度】

简单

三【题目编号】

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$
$n u m 1$ 和 $n u m 2$ 都只包含数字 $0 - 9$
$n u m 1$ 和 $n u m 2$ 都不包含任何前导零

七【解题思路】

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

八【时空频度】

时间复杂度： $O (ma x (m, n))$ ， $m$ 和 $n$ 分别为字符串1和字符串2的长度
空间复杂度： $O (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();
    }
}

Python语言版

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

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;
    }
};