昨天面试了一家公式，面试上来问我，使用过哪些STL容器，我说了一下，然后又问从最简单的开始说。
面试官：说说使用vector是需要注意什么？
我：注意什么......。迭代器失效问题。
面试官：你是看面经的吧
我：我没有看面经，平时就刷题用用这些容器，使用时需要注意什么，使用时需要注意什么（我连说两遍），平时就是用，没注意到有什么。
面试官：好吧，有看过STL源码剖析吗？
我：内心：我刷过侯捷老师的视频，但是书没看过，看的比较久了，基本上已经忘了。于是脱口而出，没看过。
面试官：好吧，你有了解什么性能优化的工具吗
我：我注意到贵公司的笔试题中有类似的问题，我就只知道valgrind，但是没用过。
面试官：好吧，那你做完笔试，有没有了解过呢？
我：没有。
面试官呵呵一笑：那你了解图吗？
我：图我就知道有向图、无向图，图的算法：迪杰斯特拉、克鲁斯卡尔（没记错的话）
面试官：图的存储呢？
我：邻接表，邻接矩阵
面试官：那什么时候用邻接表、邻接矩阵呢？
我：秋招这么久，没有面试官问过我关于图的算法，这几个算法是我之前看的。现在有点忘了。
面试官：（很惊讶），竟然没有人问过你图，好吧。你有参与过或者做过什么开源的项目吗？
我：项目没有做过，看过levelDB源码中的切片和内存分配部分。
面试官：好吧，那我们先做一道在线编程，我看看你的编程习惯，你用你熟悉的环境。
我：我熟练的打开VS，面试官把题发了过来
给定一个正整数集合S。该集合中的元素很多（大于100万)，而且该集合满足以下条件：
条件A: 集合中的所有元素之和能被正整数P=5整除。?
1.请你设计并实现一个程序，求出S的一个最小子集（最小的定义是集合元素个数最少）T，使得T也满足条件A. ?
示例：当P=5的时候，
如果
Case1: 输入 S = {1, 2, 3, 4, 5}, 则输出 T = {5} (元素个数为１）
Case2: 输入 S = {1,2,3,4}, 则输出 T = {1, 4} 或 T = {2, 3}
Case3: ?输入 S = {1,2,6,7,12,17}, 则输出 T = {1,2,7} 或 T = {6,12,17}
Case4: ?输入 S = {1,2,6,7,11, 12,13, 14, 17, 22}, 则输出 T = {1,14} 或 T = {2, 13}?...?
注意：任意输出一个最小子集即可，不要求输出所有的最小子集。
我最开始想的是暴力，思考了有3-5min，发现不行，后来想到可以用回溯求出所有子集，然后再根据子集去找，写了半天，没写出来怎么求子集（真是蠢，平时都可以的），后面面试官说了他的思路，先按下不提，我这里先把自己的思路再写写。
（1）首先求子集；
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 求最小子集的和被5整除
vector<vector<int>> res; // 存放所有子集
vector<int> path; // 存放子集
void helper(vector<int>& nums, int index) {
res.push_back(path);
// 终止条件
if (index >= nums.size()) {
return;
}
for (int i = index; i < nums.size(); i++) {
path.push_back(nums[i]);
helper(nums, i + 1);
path.pop_back();
}
}
int main(int argc, char** argv) {
res.clear();
path.clear();
vector<int> nums = { 1,2,3,4,5 };
helper(nums, 0);
for (int i = 0; i < res.size(); i++) {
for (int j = 0; j < res[i].size(); j++) {
cout << res[i][j];
}
cout << endl;
}
system("pause");
return 0;
}测试
（2）对子集进行判断；
path中存储的是某个子集，res中存储的是所有子集，需要对所有子集进行遍历；需要求的是最小的子集，那么先对子集path按照个数排序
// 我这里贴是核心代码
static bool cmp(vector<int>& a, vector<int>& b) {
return a.size() < b.size();
}
sort(res.begin(), res.end(), cmp);
for (int i = 0; i < res.size(); i++) {
for (int j = 0; j < res[i].size(); j++) {
cout << res[i][j];
}
cout << endl;
}测试
（3）对子集求和，找出满足条件的最小子集
子集已经排序了，直接遍历找到第一个满足的就行
// 贴的核心代码
// 求和函数
int add(vector<int>& nums) {
int sum = 0;
for (auto num : nums) {
sum += num;
}
return sum;
}
for (int i = 0; i < res.size(); i++) {
// 去掉空集
if (res[i].size() == 0) {
continue;
}
if (add(res[i]) % 5 == 0) {
for (auto num:res[i]) {
cout << num << "\t";
}
break;
}
}测试
换一组数据
S = {1,2,6,7,11, 12,13, 14, 17, 22}
6和14是满足的，
but，使用了回溯，整个程序复杂度就提上来了，也总算写出了（苦笑）
【注：上述代码在面试过程中并没有写出来，今天早上复盘的时候才写出来的】
贴上整体代码：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/*
给定一个正整数集合S。该集合中的元素很多（大于100万)，而且该集合满足以下条件：
条件A: 集合中的所有元素之和能被正整数P=5整除。?
1.请你设计并实现一个程序，求出S的一个最小子集（最小的定义是集合元素个数最少）T，使得T也满足条件A. ?
示例：当P=5的时候，
如果
Case1: 输入 S = {1, 2, 3, 4, 5}, 则输出 T = {5} (元素个数为１）
Case2: 输入 S = {1,2,3,4}, 则输出 T = {1, 4} 或 T = {2, 3}
Case3: ?输入 S = {1,2,6,7,12,17}, 则输出 T = {1,2,7} 或 T = {6,12,17}
Case4: ?输入 S = {1,2,6,7,11, 12,13, 14, 17, 22}, 则输出 T = {1,14} 或 T = {2, 13}?...?
注意：任意输出一个最小子集即可，不要求输出所有的最小子集。
*/
// 求最小子集的和被5整除
vector<vector<int>> res; // 存放所有子集
vector<int> path; // 存放子集
void helper(vector<int>& nums, int index) {
res.push_back(path);
// 终止条件
if (index >= nums.size()) {
return;
}
for (int i = index; i < nums.size(); i++) {
path.push_back(nums[i]);
helper(nums, i + 1);
path.pop_back();
}
}
// 排序
static bool cmp(vector<int>& a, vector<int>& b) {
return a.size() < b.size();
}
// 求和函数
int add(vector<int>& nums) {
int sum = 0;
for (auto num : nums) {
sum += num;
}
return sum;
}
int main(int argc, char** argv) {
res.clear();
path.clear();
vector<int> nums = { 1,2,6,7,11, 12,13, 14, 17, 22 };
helper(nums, 0);
for (int i = 0; i < res.size(); i++) {
for (int j = 0; j < res[i].size(); j++) {
cout << res[i][j];
}
cout << endl;
}
cout << "************************" << endl;
sort(res.begin(), res.end(), cmp);
for (int i = 0; i < res.size(); i++) {
for (int j = 0; j < res[i].size(); j++) {
cout << res[i][j];
}
cout << endl;
}
cout << "************************" << endl;
for (int i = 0; i < res.size(); i++) {
// 去掉空集
if (res[i].size() == 0) {
continue;
}
if (add(res[i]) % 5 == 0) {
for (auto num:res[i]) {
cout << num << "\t";
}
break;
}
}
system("pause");
return 0;
}话接上回，我用回溯没有写出来，说了一下我的思路，面试官和我说了他的思路
【可以先预处理一波，所有数字先对5取余，得到的数字是在0-4范围内，然后再用5个桶，类似桶排序，把数字存起来，再进行判断（取余、存储我理解了，那么怎么和原数据进行对应的）】，我没有理解面试官后面的意思（苦笑），也没有顺着他的思路写出来。
面试官：你这个回溯的复杂度是多少，你了解代码的复杂度吗，
我：代码的复杂度分为时间复杂度和空间复杂度，回溯的复杂度，我还不会分析（尴尬）。
后面就聊聊我的基本情况，今年的大环境。面试官人很好，是大佬级别的。