C++ Vector 经典算法场景与代码实现

杨辉三角

原理讲解

（1）第一步

首先两数的计算肯定是没有问题的，对应两个数相加即可。从上图看见这是一个二维数组，每行的元素个数都不同，我们可以采用 vector 来开辟一个二维数组。

vector<vector<int>> 这是二维数组类型。外面的 vector 表示开辟了一定数量的类型元素，比如 vector<vector<int>> V(5)，表示 5 个 vector<int>。而里面的每个 vector<int> 又是一个类型，这样我们可以先访问外面的->里面的，达到二维数组效果。

（2）第二步，初始化

我们可以先通过下标访问里面的 vector<int>，再调用 resize 给对应的 vector<int> 开辟空间 + 初始化。

（3）计算对应的位置

可以看到左边是从下标 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();
    }
};

只出现一次的数字 III（两个数）

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};
    }
};

只出现一次的数字 II（三个数）

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;
    }
};