腾讯实习生笔试经历
腾讯实习生笔试经历
0.笔试过程
笔试是在牛客网进行线上笔试，两个小时完成五道编程题，难度不一，与顺序无关。
笔试下来感觉一道题大约半个小时左右，一共只做出来三道题，还有半小时一直在对剩下两道题干瞪眼
1.第一题
第一题是对无向图的各边染红或者黑色，要求返回图中连接的边全为红边的节点个数
用二维数组会直接爆内存（稀疏矩阵），所以要用链表，不需要储存相连结点，只需要储存相连边的颜色就行
2.第二题
第二题是给定一个链表数组，问其每一个链表分成两部分再重新连接后能否实现升序排列。
应该是最简单的问题，只要了解过链表数据结构就可以直接秒，由于只需要考虑分两段，所以直接寻找中间发生降序变化的地方就行。
- 如果发生两次以上降序变化，必定不能仅通过一次重组就达到有序
- 如果没有发生降序变化，说明本就有序
- 如果仅发生一次降序变化，需要比较两边的首尾数字大小，判断是否能够重组有序
3.第三题
第三题是给定一个非连通图，问有多少个方案在仅添加一条边的情况下将其转化成连通图。
。。。懵逼了，可以判断连通图，但是还真不知道怎么找出所有的加边方案，感觉暴力也很难解。需要学习的东西+1
因为看到图，一直在往图论那边去想，但是现在看了题解发现比想象的简单很多。
这一题是用并查集的思想，将所有内部连通的点归属为一个集合，这样最后可以得到n个连通块，如果n>2，说明无法通过一条边令其成为连通图。n=1时，两边的节点个数分别为a和b，可以通过a*b来计算方案个数
被无向图的描述误导了，思维还是太局限了。
第三题扩展
和上面的题非常类似，思路是一样的。 给你一个 n 个点，m 条边的无向图，求至少要在这个的基础上加多少条无向边使得任意两个点可达 扩展题
4.第四题
给定一个长度为n的数组，将其分为k段，每一段内的数逐个进行位异或计算，再将每一段得到的数求和。问能够得到的最大的数是多少。
龟龟，傻眼了，前两天刚好探讨了一下加法和异或运算的联系，这里考到了，但是完全不会做。应该是最难题。
毫无疑问是臭名昭著的dp问题，在解决这个问题之前，我们要先明确一下异或计算的特性
- 可交换：, 即x^y=y^x
- 可结合：,即x^y^z可以任意结合
- 逆运算: 对于，任意交换其中两个数，仍成立，如，因此可以通过结果z反求x或y
回到原题上面，总体解题思路是动态规划
用一个二维dp数组对结果进行维护，对于dp[n][k],表示前n个数分成k段得到的最大结果
后面鸽了，找不到原题不好落实想法
5.第五题
给定一个字符矩阵，从任意一个位置出发，可以向上下左右任意一个方向移动（不能超出矩阵），要求找出能够形成tencent序列单词的数量。
用二维char储存，然后确定起点（或者终点），直接暴力递归解pass了，不知道有没有更好的方案。