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]。这样做有巨大优势计算对齐加法、乘法都是从低位开始的。逆序存储让数组的遍历方向从下标0开始递增与计算方向完全一致。进位处理产生的进位可以非常自然地添加到下一位的计算中只需要向后下标增大的方向推进即可。动态扩展如果最高位计算后还有进位我们只需要在数组末尾push_back一个新元素这非常符合std::vector的操作逻辑。因此我们的实现将采用逆序存储。我们将使用std::vectorint来存储大整数的每一位十进制数字。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::vectorint 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); };这个类包含以下核心部分私有成员digits一个vectorint用于逆序存储数字的每一位。私有成员isNegative标识正负。为了专注于加法核心逻辑我们暂时假设所有输入都是非负整数。带符号的加法会复杂很多需要先判断符号然后可能转为减法。我们把它作为后续的扩展点。构造函数最重要的就是从字符串构造因为大整数最常用的输入方式就是字符串。removeLeadingZeros这是一个至关重要的辅助函数。在运算过程中可能会产生无效的前导零例如000123在逆序存储下是[3,2,1,0,0,0]。我们需要清除它们以保持表示的规范。toString将内部的逆序数组转换回人类可读的正序字符串。运算符重载我们重载运算符使得两个BigInt对象可以像普通整数一样相加。输出重载方便用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: vectorint twoSum(vectorint nums, int target) { unordered_mapint,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(pairint,int(nums[i],i)); } return {}; } };
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]。这样做有巨大优势计算对齐加法、乘法都是从低位开始的。逆序存储让数组的遍历方向从下标0开始递增与计算方向完全一致。进位处理产生的进位可以非常自然地添加到下一位的计算中只需要向后下标增大的方向推进即可。动态扩展如果最高位计算后还有进位我们只需要在数组末尾push_back一个新元素这非常符合std::vector的操作逻辑。因此我们的实现将采用逆序存储。我们将使用std::vectorint来存储大整数的每一位十进制数字。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::vectorint 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); };这个类包含以下核心部分私有成员digits一个vectorint用于逆序存储数字的每一位。私有成员isNegative标识正负。为了专注于加法核心逻辑我们暂时假设所有输入都是非负整数。带符号的加法会复杂很多需要先判断符号然后可能转为减法。我们把它作为后续的扩展点。构造函数最重要的就是从字符串构造因为大整数最常用的输入方式就是字符串。removeLeadingZeros这是一个至关重要的辅助函数。在运算过程中可能会产生无效的前导零例如000123在逆序存储下是[3,2,1,0,0,0]。我们需要清除它们以保持表示的规范。toString将内部的逆序数组转换回人类可读的正序字符串。运算符重载我们重载运算符使得两个BigInt对象可以像普通整数一样相加。输出重载方便用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: vectorint twoSum(vectorint nums, int target) { unordered_mapint,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(pairint,int(nums[i],i)); } return {}; } };
)
