企业官网建设流程全解析

1. 从“溢出”到“字符串”：为什么需要大整数加法

在C++里，int类型通常占4个字节，能表示的最大整数大约是21亿。long long呢？大约是922亿亿。这个数字听起来很大，但在处理天文数据、密码学、高精度计算或者某些在线评测系统的题目时，这点范围可能连塞牙缝都不够。比如，让你计算两个1000位十进制数的和，用内置的整数类型直接相加，结果必然是溢出，得到一堆毫无意义的乱码。

这就是大整数（Big Integer）运算存在的根本原因：当我们需要处理的整数大小超出了计算机基本数据类型（如int,long long）的表示范围时，就必须用其他方式来模拟整数的运算。大整数加法是所有大数运算（减法、乘法、除法、模运算）的基石，也是最容易理解和实现的一个。

它的核心思路非常直观，就是我们小学时学的竖式加法。我们把一个超长的数字，比如“12345678901234567890”，看作一个字符串或者一个由单个数字组成的数组。然后从最低位（个位）开始，逐位相加，并处理进位。这个思路本身不复杂，但要把这个思路用代码严谨、高效、无Bug地实现出来，里面有不少细节值得深究。比如，数字的存储方式（正序还是逆序）、进位的处理、前导零的清除，以及如何设计一个易用的接口。接下来，我们就一步步拆解，并用C++实现一个功能完整的大整数加法。

2. 核心设计：如何表示和存储一个大整数

在动手写代码之前，我们必须先解决一个基础问题：在计算机内存中，用什么结构来代表一个“大整数”？

最自然的选择是字符串（std::string）。因为输入通常就是字符串形式，直观且易于处理每一位数字。但直接操作字符串进行运算并不方便，我们通常需要将其转换为数字数组。

这里有一个关键的设计决策：数组应该以正序还是逆序存储数字？

• 正序存储：数组下标0存储最高位（最左边的数字）。这符合人类的阅读习惯。但是，当我们做加法时，是从最低位开始的。这意味着我们需要从数组的末尾开始计算，或者先反转数组。这会给编码带来一些麻烦，尤其是处理两个数位数不同的情况时，对齐操作会变得复杂。
• 逆序存储：这是更常见且推荐的做法。我们让数组下标0存储最低位（个位）。例如，数字“12345”会被存储为[5, 4, 3, 2, 1]。这样做有巨大优势：
  1. 计算对齐：加法、乘法都是从低位开始的。逆序存储让数组的遍历方向（从下标0开始递增）与计算方向完全一致。
  2. 进位处理：产生的进位可以非常自然地添加到下一位的计算中，只需要向后（下标增大的方向）推进即可。
  3. 动态扩展：如果最高位计算后还有进位，我们只需要在数组末尾push_back一个新元素，这非常符合std::vector的操作逻辑。

因此，我们的实现将采用逆序存储。我们将使用std::vector<int>来存储大整数的每一位十进制数字。vector[0]是个位，vector[1]是十位，以此类推。

注意：这里存储的是int，但每个元素的值范围是0-9。理论上用char或short更省空间，但用int在计算中间过程（特别是涉及乘法和进位时）更方便，且现代计算机上差异不大。清晰和不易出错是首要目标。

3. 从零构建：大整数加法类（BigInt）的框架

一个好的实践是将大整数封装成一个类，这样数据（数字数组）和操作（加法、输出等）可以绑定在一起，代码更清晰，也更容易扩展。我们先搭建这个类的骨架。

#include <iostream> #include <string> #include <vector> #include <algorithm> // 用于reverse class BigInt { private: std::vector<int> digits; // 逆序存储每一位数字 bool isNegative; // 符号位，为简化我们先实现非负数的加法 public: // 构造函数们 BigInt() : isNegative(false) {} // 默认构造为0 BigInt(const std::string& s); // 从字符串构造 BigInt(long long num); // 从普通整数构造（可选） // 工具函数 void removeLeadingZeros(); // 清除逆序表示下的前导零（实际上是在数组尾部） std::string toString() const; // 转换为正序的字符串用于输出 // 算术运算符重载（目前只实现加法） BigInt operator+(const BigInt& other) const; // 为了方便测试，可以重载输出运算符 friend std::ostream& operator<<(std::ostream& os, const BigInt& num); };

这个类包含以下核心部分：

1. 私有成员digits：一个vector<int>，用于逆序存储数字的每一位。
2. 私有成员isNegative：标识正负。为了专注于加法核心逻辑，我们暂时假设所有输入都是非负整数。带符号的加法会复杂很多，需要先判断符号，然后可能转为减法。我们把它作为后续的扩展点。
3. 构造函数：最重要的就是从字符串构造，因为大整数最常用的输入方式就是字符串。
4. removeLeadingZeros：这是一个至关重要的辅助函数。在运算过程中，可能会产生无效的前导零（例如，000123在逆序存储下是[3,2,1,0,0,0]）。我们需要清除它们以保持表示的规范。
5. toString：将内部的逆序数组转换回人类可读的正序字符串。
6. 运算符重载：我们重载+运算符，使得两个BigInt对象可以像普通整数一样相加。
7. 输出重载：方便用cout << a << endl;的方式打印结果。

4. 关键实现一：构造与清理（字符串解析与前导零处理）

4.1 从字符串构造（BigInt(const std::string& s)）

这个构造函数负责将如"123456"这样的字符串，转换成逆序存储的数组[6,5,4,3,2,1]。

BigInt::BigInt(const std::string& s) { // 先处理可能的符号，这里先简单处理，假设输入都是非负整数 // 更健壮的实现应该处理 '+'、'-' 号以及非法字符 std::string numStr = s; isNegative = false; // 简单判断负号，后续完善 // if (!s.empty() && s[0] == '-') { // isNegative = true; // numStr = s.substr(1); // } else if (!s.empty() && s[0] == '+') { // numStr = s.substr(1); // } // 逆序读取字符串，将字符数字转换为整数存入digits for (int i = numStr.size() - 1; i >= 0; --i) { char c = numStr[i]; if (c < '0' || c > '9') { // 在实际项目中，这里应该抛出异常或进行错误处理 // 为了示例简单，我们假设输入总是# 1. 两数之和 ## 题目 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。 ## 思路 * 使用哈希表 将数组中的元素作为key 下标作为value * 遍历数组 如果target - nums[i] 在哈希表中存在 那么返回两个下标 * 否则将当前元素和下标存入哈希表 ## 代码 ```cpp class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int,int> map; for(int i = 0; i < nums.size(); i++) { auto iter = map.find(target - nums[i]); if(iter != map.end()) { return {iter->second,i}; } map.insert(pair<int,int>(nums[i],i)); } return {}; } };