【C++经典例题】大数相加：从基础实现到性能优化

           💓 博客主页：倔强的石头的CSDN主页

           📝Gitee主页：倔强的石头的gitee主页

⏩ 文章专栏：C++经典例题

    期待您的关注

问题背景

基础版实现

代码示例

实现思路

存在的问题

尾插优化版

代码示例

优化思路

复杂度分析

扩容优化版

代码示例

优化思路

复杂度分析

总结

问题背景

在实际编程中，我们常常会遇到需要处理大整数相加的情况。由于编程语言中基本数据类型所能表示的整数范围有限，当需要处理的整数超出这个范围时，我们就不能直接使用基本数据类型进行计算。

此时，我们可以将大整数以字符串的形式存储，通过逐位相加的方式来实现大整数的加法运算。

本文将围绕这个问题，详细介绍三种不同实现方式，从基础版逐步优化到性能更优的版本。

基础版实现

代码示例

class Solution {
public:string addStrings(string num1, string num2) {int end1 = num1.size() - 1;;//从字符串尾部遍历int end2 = num2.size() - 1;int next = 0;//进位string s;while (end1 >= 0 || end2 >= 0 )//两个字符串都遍历完成才结束{int n1 = end1 >= 0 ? num1[end1--] - '0' : 0;//先判断下标是否合法，防止越界int n2 = end2 >= 0 ? num2[end2--] - '0' : 0;int ret = n1 + n2 + next;next = ret / 10;ret = ret % 10;s.insert(0, 1, ret + '0');}if (next == 1){s.insert(0, 1, '1');}return s;}
};

实现思路

初始化：首先，我们需要找到两个字符串的末尾位置 end1 和 end2，从这里开始逐位相加。同时，我们还需要一个变量 next 来记录进位，初始值为 0。另外，我们创建一个空字符串 s 用于存储相加的结果。
逐位相加：使用 while 循环，只要两个字符串中有一个还未遍历完，就继续循环。在每次循环中，我们先判断当前下标是否合法，如果合法则取出对应位置的数字，否则将其视为 0。然后将这两个数字与进位 next 相加，得到当前位的和 ret。接着，更新进位 next 为 ret 除以 10 的结果，ret 则取 ret 对 10 取模的结果。最后，将 ret 转换为字符并插入到字符串 s 的开头。
处理最后进位：循环结束后，我们需要检查是否还有进位，如果有则将其插入到字符串 s 的开头。

存在的问题

这种实现方式的时间复杂度较高，主要是因为在字符串 s 的开头插入字符的操作会导致字符串元素的移动，时间复杂度为O（n），其中 n是字符串的长度。因此，总的时间复杂度为 O（n²）。

尾插优化版

代码示例

class Solution {
public:string addStrings(string num1, string num2){int end1 = num1.size() - 1;;//从字符串尾部遍历int end2 = num2.size() - 1;int next = 0;//进位string s;while (end1 >= 0 || end2 >= 0)//两个字符串都遍历完成才结束{int n1 = end1 >= 0 ? num1[end1--] - '0' : 0;//先判断下标是否合法，防止越界int n2 = end2 >= 0 ? num2[end2--] - '0' : 0;int ret = n1 + n2 + next;next = ret / 10;ret = ret % 10;s += ret + '0';//先尾插}if (next!=0)//防止丢失最后进位的数{s += next + '0';}reverse(s.begin(), s.end());//再反转return s;}
};

优化思路

为了避免在字符串开头插入字符带来的性能开销，我们可以采用尾插的方式：

在每次循环中，将当前位的结果字符直接添加到字符串 s 的末尾，这样时间复杂度为O（n）。循环结束后，由于结果是从低位到高位添加到字符串中的，所以我们需要将字符串反转，得到正确的顺序。

复杂度分析

这种实现方式的时间复杂度为 O（n），其中是两个字符串中较长的那个的长度。因为我们只需要遍历一次字符串，并且尾插和反转操作的时间复杂度都是O（n）。

扩容优化版

代码示例

class Solution {
public:string addStrings(string num1, string num2){int end1 = num1.size() - 1;;//从字符串尾部遍历int end2 = num2.size() - 1;int next = 0;//进位string s;s.reserve(max(num1.size(), num2.size()) + 1);//直接一次扩容完成while (end1 >= 0 || end2 >= 0)//两个字符串都遍历完成才结束{int n1 = end1 >= 0 ? num1[end1--] - '0' : 0;//先判断下标是否合法，防止越界int n2 = end2 >= 0 ? num2[end2--] - '0' : 0;int ret = n1 + n2 + next;next = ret / 10;ret = ret % 10;s += ret + '0';//先尾插}if (next!=0)//防止丢失最后进位的数{s += next + '0';}reverse(s.begin(), s.end());//再反转return s;}
};