菜鸡的2020年腾讯实习笔试数据结构与算法KnightHONG的博客-

2020年4月26日的腾讯实习生笔试，一共有五道题，给了两个小时。感觉都比较简单，甚至没有粤澳CPC的网络赛难，但是我太菜了，只做出了三道题。
第一道题是签到题：(每一道题我都wa了一遍，可能是紧张导致的？)

1. 模拟队列 输入t，有t组数据 输入n，代表有n个操作 操作有5个：SIZE，CLEAR，PUSH X，POP，TOP。 SIZE：输出队列大小 CLEAR：清空队列不输出 PUSH X：把X放进队列(1<=x<=1000) POP：把头元素拿掉 如果为空输出-1 TOP：输出头元素（不拿掉），如果为空输出-1 样例 1 PUSH 1 PUSH 2 TOP POP TOP CLEAR 输出： 1 2 

第二道题主要是我太菜了，搞不懂，刚开始想着贪心一下，然后O(n^2)跑两个for，肯定tle，然后想着加个退出条件，但是还是过不了，orz，我太年轻了，过了0个样例，后面直接暴力去跑一边，过了60%的case，不知道笔试怎么算分的，题没过但是过了一些case，不知道算不算成绩，这题没整出来。

2. 给2组点集取名为A点集和B点集，现在从A和B中选取一个，     求两点间距离的最小值 输入t，有t组数据 输入n，代表点集A和B都有n个 n行为A点集，n行为B点集 保留三位小数 1<=N<=100000 -10^9<=X,Y<=10^9 样例（瞎编，忘了） 1 2 1 1 2 2 5 5 10 10 输出 4.243 

第三题n这个值很小，我一开始就觉得是跑个dfs，然后就开始敲代码，刚开始是设置了两个状态，一个是不移动，另一个是和下一个进行交换。然后交了一发，过了10%还是20%的样例，然后又想到一种情况，假设现在有卡牌ABC，我现在在B这个位置，我B和C换后，就变成了ACB然后我C再和A换就变成了CAB了，时间关系，我没有仔细思考完这道题，最后是只过了30%的case。

3. 现在有一套卡牌，从左到右排开，卡牌有正反面，正面的值为ai，  反面的值为bi，可以翻转相邻的卡牌，翻转的规则：先相互交换位置，  然后都翻面。现在求最小的操作次数，确保从左到右不为降序。   输入n，代表有n个数（n<=18） 接下来有两行 ，每行n个数，第一行为a序列，第二行为b序列 样例 3 1 3 2 1 3 2 输出： 1 

第四道题和第一道题签到题类似了。用两个栈模拟队列。我们设置两个栈S1,S2。在我们push操作的时候，就放入S1这个栈，如果需要poll和peek操作的时候，我们把S1的数据倒入S2，在S2进行操作poll和peek，操作完后，再把S2倒回S1就完成了模拟队列了。

4. 用两个栈模拟队列 peek操作为输出队列的头元素 poll操作为去掉头元素 push x操作为把x放入队列 输入q（1<=q<=10^5）(-10^?<=x<=10^?)(?为忘记了，不过依稀记得?>=5) 输出要求： 当操作为peek时，输出头元素 样例 5 push 1 push 2 push 3 peek poll peek 输出： 1 2 

最后一道题不难，题目给的是一颗满二叉树，全部节点都会有。在当前节点除以2就是它的父节点了，我们一直这样进行“ /2 ”操作，最后就会回到根节点：1。然后把这些节点保存道一个数组里，数组最后一个数字就是深度为1的节点。虽然数据有10¹⁸，但是对于一颗满二叉树来说，它的深度其实并不大。复杂度O(log₂n)

2ⁿ=10¹⁸(n是深度)
n = log₂10¹⁸
n = 18*log₂10
3< log₂10 <4
54<n<72
数组也就开到72左右的大小就足够了

5. 给你一个满二叉树 例：（1节点，2节点，3节点***********）      1 2 3 4 5 6 7 ----------- 现在输入一个n，代表第n节点，输入一个x代表深度。（1<=n<=10^18） 判断n节点存不存在深度为x的父节点（或祖父节点，曾祖父节点*****） 有则输出节点编号，没有输出-1 样例 10 1 10 2 10 3 10 4 输出 1 2 5 -1 

总结：自己太菜了，要提升的太多了，弱鸡快要窒息了，又酸又菜又多鱼，继续加油吧~