C++算法
C++ Vector 经典算法场景与代码实现
深入解析 C++ STL 中 Vector 在经典算法题中的应用。涵盖按位异或解决单一数字查找问题、二维 Vector 构建杨辉三角、递归实现电话号码字母组合、利用 unique 加 erase 进行整型去重，以及针对多个数字出现特定次数的位运算优化方案。文章提供详细原理讲解与完整代码示例，帮助开发者掌握 Vector 底层机制及性能优化技巧。
深入解析 C++ STL 中 Vector 在经典算法题中的应用。涵盖按位异或解决单一数字查找问题、二维 Vector 构建杨辉三角、递归实现电话号码字母组合、利用 unique 加 erase 进行整型去重，以及针对多个数字出现特定次数的位运算优化方案。文章提供详细原理讲解与完整代码示例，帮助开发者掌握 Vector 底层机制及性能优化技巧。
https://leetcode.cn/problems/single-number
这种题可以通过排序来找，但最高效的是按位异或：^
**按位异或原理：**比较二进制，相同为 0，相异为 1，如果两个数字一模一样去异或，那么就可以消除。
class Solution {
public:
int singleNumber(vector<int>& nums) {
int tmp = 0;
for (int i = 0; i < nums.size(); i++) {
tmp ^= nums[i];
}
return tmp;
}
};
当然用范围 for、迭代器也是可以的，因为也是遍历（支持迭代器就支持范围 for）。
class Solution {
public:
int singleNumber(vector<int>& nums) {
int tmp = 0;
// 范围 for
for (auto e : nums) {
tmp ^= e;
}
return tmp;
}
};
class Solution {
public:
int singleNumber(vector<int>& nums) {
int tmp = 0;
// 迭代器
auto it = nums.begin();
while (it != nums.end()) {
tmp ^= (*it);
it++;
}
return tmp;
}
};
首先两数的计算肯定是没有问题的，对应两个数相加即可。从上图看见这是一个二维数组，每行的元素个数都不同，我们可以采用 vector 来开辟一个二维数组。
vector<vector<int>> 这是二维数组类型。外面的 vector 表示开辟了一定数量的类型元素，比如 vector<vector<int>> V(5)，表示 5 个 vector<int>。而里面的每个 vector<int> 又是一个类型，这样我们可以先访问外面的->里面的，达到二维数组效果。
我们可以先通过下标访问里面的 vector<int>，再调用 resize 给对应的 vector<int> 开辟空间 + 初始化。
可以看到左边是从下标 2 开始，右边是从下标 1 开始，那么空格的元素为【i-1,j-1】+【i-1,j】之和。
class Solution {
public:
vector<vector<int>> generate(int numRows) {
// 开辟行数
vector<vector<int>> V(numRows);
// 开辟二维数组 (开辟 + 初始化)
for (int i = 0; i < numRows; i++) {
V[i].resize(i + 1, 1);
}
// 计算指定元素
for (int i = 2; i < numRows; i++) {
for (int j = 1; j < i; j++) {
V[i][j] = V[i - 1][j] + V[i - 1][j - 1];
}
}
return V;
}
};
https://leetcode.cn/problems/letter-combinations-of-a-phone-number
题目解读：
我们可以看到每个数字都代表着一串字符，题目会给你一串字符数字，让你用这些数字所映射的字符串去根据里面的字符组合出不同的字符串。例如：给你'34'。3 代表'def'，4 代表'ghi'，它们可以组合出：'dg'、'dh'、'di'、'eg'、'eh'、'ei'、'fg'、'fh'、'fi'，将这些字符串放在 vector 里面，返回即可。
这题需要用到多参的递归。
（1）首先我们需要表达映射关系，比如'2'对应'abc'，'3'对应'def'，以此类推。
// 映射关系
string str[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
（2）递归函数参数：题目给的数字组合、数字下标、组合的字符串、vector存储。
参数的解释：digits 方便我们找到数字字母、val 为数字下标、news 是组合得到的字符串。
（3）首先要拿到第一位数字字母映射的内容，由数字下标找到数字映射的字符串。
// 拿到映射内容
int tmp = digits[val] - '0';
string stll = str[tmp];
（4）此时我们可以通过循环控制当前的字符：def，例如：
// 从第一个字母开始组合
for (int i = 0; i < stll.size(); i++) {
// 进入第二层 for 循环
}
此时 i 为 0，也就是指向 d，下面我们想组合出 dg、dh、di，还需要调用递归函数。
（5）函数的参数：
Compare(digits, val + 1, news + stll[i], V);
ghi 是第二个数字映射的字符串，但是又不能真正改变 val，因为后面要回溯。 此时相当于 news 从原来的 "" 变成了 "d"，也不能真正改变 news，因为后面要回溯否则就累积了。
（6）现在是递归的结束条件，如果组合完每层的字母，那就返回，回到第一层 for 循环，重新开始。
// 递归结束条件
if (val == digits.size()) {
// 存储
V.push_back(news);
return;
}
class Solution {
// 映射关系
string str[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
public:
// 递归函数
void Compare(string digits, int val, string news, vector<string>& V) {
// 递归结束条件
if (val == digits.size()) {
// 存储
V.push_back(news);
return;
}
// 拿到映射内容
int tmp = digits[val] - '0';
string stll = str[tmp];
// 从第一个字母开始组合
for (int i = 0; i < stll.size(); ++i) {
// 进入第二层 for 循环
Compare(digits, val + 1, news + stll[i], V);
}
}
vector<string> letterCombinations(string digits) {
vector<string> V;
if (digits.empty()) {
return V;
}
// 调用递归函数
Compare(digits, 0, "", V);
// 返回结果
return V;
}
};
https://leetcode.cn/problems/remove-duplicates-from-sorted-array
（1）首先我们不管此类去重题有没有序，如果没有，调用 Sort 函数先排序。
（2）如果本身已经有序，使用：unique+erase 去重组合即可（适用任何类型）。
unique 接口作用： 返回一个迭代器，指向去重后序列的末尾（即最后一个不重复元素的下一个位置）。
unique 接口参数： 序列范围：begin（），end（）。
erase 接口作用： 指定删除范围内的元素，并将之后的元素前移。
注意： unique 的范围必须有序，且必须保存返回值作为 erase 的输入范围点。 erase 之后迭代器会失效，如果需要重复使用，需要接收 erase 的返回值。
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
auto new_end = unique(nums.begin(), nums.end());
nums.erase(new_end, nums.end());
return nums.size();
}
};
https://leetcode.cn/problems/single-number-iii
（1）先算出不同的两个整型的异或结果（比如：1、2、1、3、2、5，异或和结果为 6）。
（2）找到最低位的 1（注意整型溢出）。
int mask = (tmp == INT_MIN ? tmp : tmp & (-tmp));
（3）将最低位为 1 的进行分组，最后得到只出现一次的两个数字。
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
// 计算异或和
int tmp = 0;
for (auto e : nums) {
tmp ^= e;
}
// 算最低位的 1
int mask = (tmp == INT_MIN ? tmp : tmp & (-tmp));
// 分组异或
int a = 0;
int b = 0;
for (auto e : nums) {
if (e & mask) {
a ^= e;
} else {
b ^= e;
}
}
return {a, b};
}
};
https://leetcode.cn/problems/single-number-ii
出现 3 次的数字它的该位加起来至少是 3，例如：统计每一位上 1 出现的次数，对 3 取模，剩下的即为只出现一次的数字。
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ans = 0;
// 遍历二进制的每一位
for (int i = 0; i < 32; ++i) {
int total = 0;
for (auto num : nums) {
// 统计该位 1 的个数
total += ((num >> i) & 1);
}
// 模 3 去重
if (total % 3) {
ans |= (1 << i);
}
}
return ans;
}
};
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online