NC1 大数加法

题目

描述：以字符串的形式读入两个数字，编写一个函数计算它们的和，以字符串形式返回。

数据范围：s.length,t.length≤100000，字符串仅由'0'~‘9’构成

要求：时间复杂度 O(n)

示例1

输入：
"1","99"
返回值：
"100"
说明：
1+99=100

示例2

输入：
"114514",""
返回值：
"114514"

解题思路

1. 从字符串的最后一个字符开始遍历，每次从两个字符串里分别取出一个字符，进行相加。
2. 需要判断是否有下位数的进位，如果有需要加上进位。
3. 如果结果 >= 10，需要进行取模运算，得到个位数的值，把个位数记录到结果字符串里，需要记录取模运算的结果。

第一版源码

    string solve_old(string s, string t) {
        // write code here
        // return std::to_string(std::stoi(s) + std::stoi(t));
        // string s = "999", t = "100";
        auto sit = s.rbegin();
        auto tit = t.rbegin();

        string res; // 考虑优先分配好空间?
        int carry = 0; // 记录进位

        // 考虑使用下标？ 代码更简洁
        // 优先分配空间后，考虑从最后一个空间开始？ 避免反转
        while (sit != s.rend() && tit != t.rend()) {
            int tempRes = (int)(*sit - 48) + (int)(*tit - 48) + carry;
            carry = tempRes / 10;
            sit++;
            tit++;
            res += (char)(tempRes % 10 + 48);
        }

        while (sit != s.rend()) {
            int tempRes = (int)(*sit - 48) + carry;
            carry = tempRes / 10;
            res += (char)(tempRes % 10 + 48);
            sit++;
        }

        while (tit != t.rend()) {
            int tempRes = (int)(*tit - 48) + carry;
            carry = tempRes / 10;
            res += (char)(tempRes % 10 + 48);
            tit++;
        }

        if (carry != 0) {
            res += (char)(carry + 48);
        }

        std::reverse(res.begin(), res.end()); // 反转

        return res;
    }

可以看出，代码有很多重复的地方，我们进一步优化

存在的问题

• 如果字符串很长的话，会动态的修改存储结果的字符串的大小
• 我们在第一版使用了三个while循环, 存在重复代码.
• 我们最后是进行了字符串反转的

解决思路

• 提前分配好空间
• 使用索引来代替迭代器
• 由于提前分配好了空间, 我们可以把结果从结果字符串的最后一位空间开始向前存储

第二版源码

    string solve_old1(string s, string t) {
        // 数组最后以一个元素的下标
        int sindex = s.size() - 1;
        int tindex = t.size() - 1;

        // 计算最大长度
        int maxLen = sindex > tindex ? sindex + 1 : tindex + 1;

        string str(maxLen + 1,'0'); // 提前分配好空间，比最长多一，考虑进位
        int carry = 0;               // 记录进位
        while (sindex >= 0 || tindex >= 0) {
            int tempSum = 0; // 记录临时和
            if (sindex >= 0) {
                tempSum += s[sindex--] - '0';
            }
            if (tindex >= 0) {
                tempSum += t[tindex--] - '0';
            }
            tempSum += carry;
            carry = tempSum / 10;
            str[maxLen--] = tempSum % 10 + '0';
        }

        if (carry != 0) {
            str[maxLen] = carry + '0';
        } else {
            str.erase(maxLen, 1);
        }

        return str;
    }

感觉空间利用率不高，我们复用参数字符串的空间，不在自己去重新创建空间。

最终版

    string solve(string s, string t) {
        // 数组最后以一个元素的下标
        int sindex = s.size() - 1;
        int tindex = t.size() - 1;
        // 计算最大长度
        int endIndex = sindex > tindex ? sindex : tindex;
        string str = sindex > tindex ? s : t; // 合理利用已经存在的空间

        // string str(maxLen + 1, '0'); // 提前分配好空间，比最长多一，考虑进位
        int carry = 0;               // 记录进位
        while (sindex >= 0 || tindex >= 0) {
            int tempSum = 0; // 记录临时和
            if (sindex >= 0) {
                tempSum += s[sindex--] - '0';
            }
            if (tindex >= 0) {
                tempSum += t[tindex--] - '0';
            }
            tempSum += carry;
            carry = tempSum / 10;
            str[endIndex--] = tempSum % 10 + '0';
        }

        // 最高位进位
        if (carry != 0) {
            str.insert(str.begin(), carry + '0'); // 在最前面插入
        }

        return str;
    }