前段时间投了腾讯互娱群下的天美工作室，结果10分钟不到就收到了面试通知，约到四天后的晚上，我甚是期待，奈何这次面试给我上了一课，足足面试了我三个半小时多，而且还凉凉了，真是身心疲惫呀。
首先面试一开始，面试官给我直接说我们先来作题，我心想怕是动态规划的题就凉凉，果然面试官给了我三道题，第一题就是动态规划，看了一眼果断进军第二题。
第一题、获得目标数的总和
给你一个非负的数组nums，和一个key值，你可以再nums中每两个数中间任意加入`-`或者`+`，使得其运算可以得到目标数key，请你返回能得到目标数key的所有方法的总和。
首先想到深度优先，遍历nums，从开头开始+，只要小于key并且没有达到数组尾部，就继续加，直到大于key返回上一层变为-后继续向后+，以此类推，但是结果时间超时。而且废了我20分钟，我立刻放弃此题写下一题。后来才知道动态规划可以解决。
我已经将第一题的思路写了一篇博客，欢迎大家提供不一样的思路动态规划01背包的拓展问题
第二题、LRU的模拟实现，要求查询，插入复杂度都是O(1)
题目链接LRU缓存
这道题我用单链表实现的，面试官看完代码就问我时间复杂度，很显然不是O(1)，他不是很满意。下来我自己想了想结合大佬提供的思路，使用list和unordered_map来实现
数据结构
size_t cap;//缓存容量list<pair<int,int>> cache;//缓存块链表unordered_map<int, list<pair<int, int>>::iterator> mp;//用来标记key值再list中迭代器的位置
思路
put的时候判断key值在mp中是否存在，不存在，则将pair<int,int> (key,value)头插到到cache的头部，如果存在，则将其取出并且插入到cache的头部。
上述执行完，只需判断当前cache.size()，是否大于容量cap,如果大于，则对list进行尾删，同时将mp中对应的key删掉。
get的时候，同样先判断当前key值在mp中是否存在，不存在则依据题目要求返回-1，否则表示存在。
接下来从mp中获取其对应的迭代器，从而获得该结点的信息，然后将该结点从这个位置删掉，再将其头插到cache中即可，再更新mp中其对应的迭代器位置即可
class LRUCache {public:LRUCache(int capacity) :cap(capacity) {}int get(int key){auto it = mp.find(key);if(it == mp.end()) return -1;auto pos = it->second;//获取当前key值在cache中对应的位置int res = pos->second;//获取value值cache.push_front(pair<int,int> (pos->first,pos->second));//将新节点头插cache.erase(pos);//删除旧节点mp[key] = cache.begin();//更新key对应的迭代器位置return res;//返回}void put(int key,int value){auto it = mp.find(key);//从mp中查询key是否存在//如果不存在，则表示要更新if(it == mp.end()){//将key和value构成一个新节点头插到cache中cache.push_front(pair<int,int> (key,value));mp[key] = cache.begin();//将key以及cache中key对应的迭代器的位置插入到mp中}//表示存在else{//获取key值当前在cache中的位置auto pos = it->second;cache.erase(pos);//删除该结点cache.push_front(pair<int,int> (key,value));//构建新的检点头插到cache中mp[key] = cache.begin();//更新mp中key在cache中国的迭代器的位置}//判断当前cache的大小是否超过capif(cache.size() > cap){//超过则对cache进行尾删mp.erase(cache.back().first);//先从mp中删除对应的key值cache.pop_back();//再进行尾删}}public:size_t cap;list<pair<int,int>> cache;unordered_map<int, list<pair<int, int>>::iterator> mp;};
第三题、有效的括号字符串
题目链接：有效的括号字符串
这个题还算友好
给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：
任何左括号 ( 必须有相应的右括号 )。任何右括号 ) 必须有相应的左括号 ( 。左括号 ( 必须在对应的右括号之前 )。* 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。一个空字符串也被视为有效字符串。
示例 1:
输入: "()"输出: True
示例 2:
输入: "(*)"输出: True
示例 3:
输入: "(*))"输出: True
注意:
字符串大小将在 [1，100] 范围内。
写这道题快完的时候网断了，重新连接上面试后之前所有代码全没了，面试官直接让我从写，从新计时一小时(心态都崩了)
言归正传，这和我之前做的一个题很类似，只不过这道题*不仅可以代替(和)还能代替空格，首选用栈，写到一半发现有种情况没考虑直接从来，又耽误了很长时间，之后使用双栈搞定
思路
定义两个栈st1和st2分别用来存储(和*的下标，那么分为以下几种情况：
如果为(则其下标入栈st1，如果为*则其下标入栈st2。如果为)则优先从st1中判断是否存在(的下标，存在则出栈，继续向下遍历字符串，如果st1为空则再判断st2中是否存在*的下标，存在则出栈，再继续向下遍历。如果st1和st2都为空，表示没有（或者*与之匹配，返回false。如果遍历完字符串后，st1为空，则返回true，否则就要和st2中的*进行匹配，当st1的栈顶元素小于st2的栈顶元素则st1和st2同时出栈，否则返回false。最后返回st1是否为空即可
class Solution {public:bool checkValidString(string s) {stack<int> st1,st2;for(int i = 0;i<s.length();i++){//如果是(或者*则入栈if(s[i] == '(')st1.push(i);else if(s[i] == '*')st2.push(i);//是)则进行匹配else{if(!st1.empty())st1.pop();else if(!st2.empty())st2.pop();elsereturn false;}}//剩下的(和*进行匹配while(!st1.empty() && !st2.empty()){if(st1.top() > st2.top())return false;st1.pop();st2.pop();}return st1.empty();}};
到这，三道题我就写了两道，其中第一道没有得到完美答案，第二道没让面试官满意。接下来开始问基础知识。
以下罗列
1.同学你了解C++的多态吗？多态是如何实现的？
2.构造函数可以是虚函数吗？为什么？
3.析构函数可以是虚函数吗？为什么？
4.快速排序的原理是什么？（霍尔划分，挖坑法，前后指针能说的都说了)
5.快排如何优化？（随机数法，三数取中，加入插入排序，递归变为非递归等能说的也都说了）
6.给你5000W数量级的数据，如何快速定位到我要找到的数据？（哈希表，B+树）
7.如果一个机器存不下5000W数量级的数据，怎么办？（当时脑子有点秀逗，答了个插入外存条，面试官直接笑了，就跳过了这个问题，现在想想，应该是使用布隆过滤器）
8.C++中提供的强制类型转换有哪些，有什么区别？
9.有了解过LINUX操作系统吗？它有什么优点？
10.Linux下I/O多路复用机制有哪些？区别是什么？（epoll，poll，select它们之间的区别）
重点来了，问完上述问题，面试官给我来了一句：前面三道题你写的不是很理想，来我们加试50分钟，再给你两道题写。
我内心：？？？？？还能加试？？？？
于是硬质头皮答应了，又给了我两个题
第一个就是自己实现memcpy函数，这个主要就是注意内存重叠的问题，拷贝的思路都么没问题，但是不知当时怎么了，犯了一个致命错误，void类型我返回了一个char*类型，导致面试官就不再看我的代码，直接看下一道题。
最后一题是以逗号为分隔符反转字符转中的单词
例如
输入：hello world,you bless god输出：world hello,god bless you
这个没什么难度，先以,为分界位置全部反转一次，再以,和空格为分界位再反转一次就行
void reverse_str(string& str,int left,int right){while(left <= right){char tmp = str[left];str[left] = str[right];str[right] = tmp;left++;right--;}}void str_reverse(string& str){int begin = 0,start = 0,end = 0,flag = 0;for(int i = 0;i<str.length();i++){if(str[i] == ' ' || str[i + 1] == '\0'){if(str[i + 1] == '\0')end = i;elseend = i - 1;flag = start;reverse_str(str,start,end);start = i + 1;}if(str[i] == ',' || str[i + 1] == '\0'){if(str[i + 1] == '\0')end = i;elseend = i - 1;if(flag != start){reverse_str(str,start,end);reverse_str(str,begin,end);start = begin = i + 1;}else{reverse_str(str,begin,end);start = begin = i + 1;}}}}
终于，面试官问我你还有什么要问我的吗？我就简单问了下工作环境以及工作量。就结束了历时三个半小时的面试，真的身心疲惫。
第二天看了眼面试流程，变灰了，就知道凉凉了，虽然没有过，但是还是学到了不少，希望今后能够面试顺利！！
如果觉得《腾讯暑期C++天美工作室游戏开发实习面试题面经》对你有帮助，请点赞、收藏，并留下你的观点哦！
