一、题目描述

NC1大数加法
题目大意：以字符串形式读入两个数字，编写一个函数计算它们的和，以字符串形式返回
注意审题：字符串长度不大于100000，保证字符串仅由'0'~'9'这10种字符组成（说明算法的之间复杂度应该控制在线性，且两个字符串表示的数是非负数）

二、算法（模拟）

解题思路

1. 本题是经典的高精度加法问题，但是不用考虑负数的情况，所以较为简单。
2. 我们可以模拟竖式加法进行运算，一开始先将两个字符串翻转，即从低位向高位计算；然后我们模拟竖式加法的原则，将对应数位的值相加，再加上上一步的进位值，假设和为d，则结果的当前位为d % 10，进位值为d / 10，以此类推
3. 我们可以发现，两个数相加的结果最多为最高数位+1，例如一个2位数和4位数相加，结果最多为5位数，以此当运算到最高数位后，进位值d可能不为0，则需要添加一位d

代码实现（C++11）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算两个数之和
     * @param s string字符串 表示第一个整数
     * @param t string字符串 表示第二个整数
     * @return string字符串
     */
    string solve(string s, string t) {
        if(s.size() < t.size()) return solve(t, s);    // 若s的长度小于t, 交换一下两者的位置
        reverse(s.begin(), s.end());    // 翻转s
        reverse(t.begin(), t.end());    // 翻转t
        string ans;    
        int d = 0;    // 进位值
        for(int i = 0; i < s.size(); i++){    // 以最大的数位基准
            d += s[i] - '0';
            if(i < t.size()) d += t[i] - '0';    // 若t当前位不为0
            ans += d % 10 + '0';    // 当前位的结果
            d /= 10;    // 下一步的进位值
        }
        if(d) ans += d % 10 + '0';    // 若d不为0，增加一位
        reverse(ans.begin(), ans.end());    // 将答案翻转
        return ans;
    }
};

时间复杂度：O(max(n, m))，n为s的长度，m为t的长度
空间复杂度：O(1)