12.29 - 字符串相加 vector和map的区别
目录
1.加字符串相
a.核心思想
b.思路
c.步骤
2.vector和map的区别
a.不同点
b.相同点
1.加字符串相
415. 字符串相加 - 力扣（LeetCode）https://leetcode.cn/problems/add-strings/
class Solution { public: string addStrings(string num1, string num2) { string result = ""; int carry = 0; int i = num1.size() - 1, j = num2.size() - 1; while (i >= 0 || j >= 0 || carry > 0) { int digit1 = (i >= 0) ? num1[i--] - '0' : 0; int digit2 = (j >= 0) ? num2[j--] - '0' : 0; int sum = digit1 + digit2 + carry; carry = sum / 10; result.insert(result.begin(), sum % 10 + '0'); } return result; } };a.核心思想
模拟手工加法的过程，从两个字符串的末尾开始逐位相加，处理进位情况，最后将结果反转得到最终的和字符串。
b.思路
① 使用两个指针分别指向两个字符串的末尾。
② 从末尾开始逐位相加，将每一位的结果模10作为当前位的值，整除10得到进位值。
③ 将每一位的结果插入到结果字符串的前面。
④ 处理完所有位后，如果还有进位，将其插入到结果字符串的最前面。
⑤ 返回结果字符串。
c.步骤
① 初始化结果字符串
result，进位carry为0，以及两个指针i和j分别指向num1和num2的末尾。② 循环直到两个指针都处理完且进位为0：
获取当前位的数字，如果指针未越界则取对应字符转换为数字，否则取0。
计算当前位的和以及进位。
将当前位的值插入到结果字符串的前面。
移动指针。
③ 返回结果字符串。
2.vector和map的区别
a.不同点
vector | map | |
数据结构与存储方式 | 本质是动态数组，在内存中是连续存储的。这种连续存储使得它能够高效地进行随机访问，通过下标直接定位元素，时间复杂度为 O(1) | 通常基于平衡二叉树（如红黑树）实现，元素以键值对的形式存储，并且会根据键的大小自动排序。由于是树形结构，其内存不是连续的 |
元素特性 | 存储的是单一类型的元素，元素之间没有特定的关联关系，只是按照插入顺序依次排列 | 存储的是键值对，每个键都是唯一的，通过键可以快速找到对应的值，键和值之间存在明确的映射关系 |
操作效率 | 在尾部进行插入和删除操作效率较高，时间复杂度通常为 O(1)；但在头部或中间插入和删除元素时，需要移动大量元素，时间复杂度为 O(n)。随机访问元素效率极高 | 插入、删除和查找操作（基于键）的时间复杂度通常为 O(log n)，因为需要遍历树结构来找到对应的位置 |
适用场景 | 适用于对元素进行顺序存储，且需要频繁进行随机访问的场景，例如存储一系列的数据点，后续需要根据索引快速获取某个数据点的值 | 适用于需要根据键快速查找对应值的场景，例如在字典应用中，通过单词（键）快速查找其释义（值） |
b.相同点
① 都是标准模板库（STL）容器：vector 和 map 都是 C++ 标准模板库中提供的容器，用于存储和管理数据，为程序员提供了方便的数据存储和操作方式。
② 都支持迭代器操作：都可以使用迭代器来遍历容器中的元素，方便对容器内的数据进行各种操作，如遍历、查找、修改等。
③ 都可以动态增长：vector 可以根据需要自动扩展其存储空间以容纳更多的元素；map 也可以动态地添加和删除键值对，适应数据的变化
希望这些内容对大家有所帮助！
感谢大家的三连支持！