4.26腾讯笔试个人做法题解

在学校卷不下去了，要没有书读了，只好来找实习碰碰运气了😂😂

因为晚上有作业deadline还没有搞定，所以笔试题写的比较急，代码规范什么的都很差，这里就不放出来丢人现眼了

就简单说下思路和一些个人感受吧

以下题解只能说在题目的数据上是可以过的，部分题解还没有特别严谨的证明，可能没有考虑到edge case，并不能说在所有情况都是OK的，如果有大佬发现我说的不太对的地方，找到了反例，也欢迎跟我交流。

第一题：

    经典队列，调STL的queue或者用数组模拟都可以

第二题：

   经典平面最近点对，只不过这里有两个集合的点，用flag标记一下只算不同集合的点的距离即可

   分治是O(nlogn)的，合并的时候需要排序，因此总体时间复杂度应该是O(nlog^2n)，不过这个复杂度依赖于那个6个点的证明

   现场比赛的时候因为着急记不清具体结论了，然后就写了个KD树看看能不能混一下，KD树是经典求解最近点对的数据结构，也比较好写

   如果我没记错的话，KD树单次查询的时间复杂度是O(sqrt(n))，所以一组数据时间复杂度应该是O(n*sqrt(n))

   但是题目里我记得没有给T的范围，数据量还是蛮大的，需要用快速读入，再卡卡KD树的常数才能过去

   后来怕如果再次评测可能会被卡常数挂几个点，九点多的时候在纸上推了下平面最近点对，写了写也过了，感觉应该是挺容易想的：

平面最近点对：

  将点按照某一维坐标排序，这里假定为x坐标，按照x坐标的顺序可以把点集分成左右两部分，这样的话答案只会有三种情况

   1、两个点都在左边

   2、两个点都在右边

   3、两个点一个在左边，一个在右边

   1和2这两种情况可以继续分治下去直到边界（只有一个点或者两个点的时候），因此只需要考虑3情况怎么算

    这里先给出做法，然后对时间复杂度进行证明，做法是根据左右分治下去的结果可以得到一个较小的解，设为d，那么所有与分界面的x坐标在x方向上的距离大于等于d的点都不可能在3情况里成为最优解，过滤掉这些点，然后对剩下的点按照y坐标排序，枚举每个点，然后按y序从小到大枚举比这个点y坐标大的点，计算两个点的距离并更新d，如果两个点在y方向上的距离大于等于d，就可以直接break

    这个做法的时间复杂度依赖于第二层枚举的点不会超过6个的这个结论的证明：

    根据算法，考虑一个在左侧的点，在右侧可能跟他算距离更新答案的点的区域是一个x方向上长d，y方向上长2d的一个矩形，

    这里需要注意根据分治更新的结果，右侧任取两个点，距离都大于等于d，现在只需要考虑这个矩形区域里面最多包含多少个点，使得任意两个点之间的距离不超过d。

    结论是相对显然的，脑补一下会发现不会超过6个点，但是如果认真证明起来比较复杂，我早上起来尝试着找一种相对简洁且严谨的证明方式，但是还没有找到，希望有大佬可以指教一下

    在这个结论下，总时间复杂度就是O(nlog^2n)了

    值得一提的是，这个题的数据看上去有点弱，平面最近点对也有一些基于随机化的非完美算法，调调迭代参数也可以过？不过这个就纯属个人口胡了，没有实际实验过

    一些可以尝试的非完美算法比如模拟退火，或者随机角度倾斜xy轴对所有点做坐标轴变换，然后根据x坐标排序，对每个点算附近常数个点的距离，然后更新答案，迭代随机倾斜角度若干次这种做法现场调调迭代次数没准也可以过题目

第三题：

    很有趣的题目，首先考虑一个简化版的问题：

    有若干个数，每次操作可以交换相邻两个数，问最少操作多少次可以形成不降序列？

    这是经典问题了，显然答案就是初始序列的逆序对数目，我记得这也是逆序对的定义之一，求逆序对有很多种O(nlogn)的做法，这里不再赘述（而且对于这个n<=18的数量级，暴力就完事了

这个题目多了个翻转操作，那么可以思考一下，如何去掉这个操作呢？

     很容易发现一个结论，因为交换和翻转操作是绑定的，因此如果知道一张牌的初始位置和结束位置，可以根据位置差的奇偶性判断这张牌是否正面朝上。简单来说，就是如果位置差为奇数，牌反面朝上，否则正面朝上

     由于数据范围并不大，我们可以枚举每张牌是否正面朝上，显然一共有2^n种情况，然后排序，这样我们可以获得每张牌的初始位置和结束位置，然后需要根据位置差的奇偶性判断可行性，对于可行的序列，问题就已经转化成了刚开始的简化版问题了，求解逆序对更新答案即可，时间复杂度是O(2^n*nlogn)

     在具体实现的时候需要注意一个细节，就是元素之间有重复，因此排序后的位置映射关系可能有多种，对于相同的数字，统计所有的初始位置和结束位置以及位置差的奇偶性需求，找到一组可行的映射方案即可。举个例子，比如重复数字有两个初始位置1和2，然后对于位置差的需求均为奇数，那么我们只需要看看终止位置是否有一个奇数，一个偶数即可。

     以上是我个人的一孔之见，没有相对特别严谨的证明，因此可能是有误的，仅仅只是在本次笔试题的数据点上可以通过，希望有大佬可以给出一个严谨的证明或者给出一个反例

     做题的时候最先想到的是状态压缩DP，但是想了想似乎需要子集枚举，时间复杂度起码是O(3^n)，感觉常数大一点可能过不去，有点害怕就没有写，不过看到别人的帖子好像子集枚举应该也是可以过去的。

第四题：

    有点懵逼，这是一个标准的双端队列，不知道为什么要求用两个栈实现。

    考试的时候直接写双端队列就过了。。早上起来的时候想了想，大概理解了两个栈的做法，但是感觉有点多此一举？常数也大了，也不易于维护，感觉有点蠢蠢的。不知道会不会审查我的代码发现我没有写两个栈扣我的分😛

第五题：

    刚开始的时候愣是没读懂题，编号为x的深度为k的祖先的编号？

    结果上手先写了个编号为x的节点在深度为k的祖先的子树下重编号后得到的编号，结果发现样例都过不去，算了下样例，总算理解了题意（感觉自己智商已经没了

    稍微推一下就OK了，没什么好说的。想不出来的话可以试着在纸上简单的画个树，然后把每个节点的二进制表示标一下，找下规律也可以，知道完全二叉树相关结论的也可以直接做

个人感受：

 萌新第一次参加这种线上笔试题，没有啥经验，以至于在答疑里问出了如何切换到上一题做题这种愚蠢的问题。考试的时候以为不能切出做题界面，特别费劲的在牛客网提供的浏览器IDE上写代码，结果第二题一开始KD树写炸了，调都没法调，后来看了下要求，发现编程题可以切出去写代码，就非常开心的用vs开始调试，很快就调出来了。感觉还是练习不够，白板写代码写写有点思维量的题目还可以，写数据结构就很容易爆炸。

  希望比较有这方面经验的大佬可以指点一下我，我个人感觉应对这种笔试从心态到策略上都不是很过关，全程在冒冷汗。