笔试内容：
笔试相对比较简单只包含五道算法题。
1.找链表公用元素
两个降序链表，找其***同拥有的元素。
样例输入：
6, 5,4,3,2,1
6,5,3,2,1
样例输出：
6,5,3,2,1
个人解法： 双指针，O(N)遍历即可
2. 找通知人数
找n个人，m个小组（每个人可以在多个小组中，也可以不在任何小组中），个人编号0~n, 给一个人发通知，在同一个小组的人能收到通知传递，问给0号发通知，输出有多少人能收到通知。
个人解法： 并查集即可
3.排key个的字符串
输入n个字符串（可能相同），按照每个字符串出现次数排序规则，问出现次数前K的字符串及其次数，和出现次数后K个的字符串及其次数。
个人解法：hash, 大小堆
4,中位数
n(偶数)的整数数组，需要输出删除其中任意一个数后数组的中位数；
如1,2,3,4,5,6， 删除1，剩下2,3,4,5,6 中位数为4.
个人解法：快排变形找出第n/2和n/2-1的数，在遍历一遍分别判读与其大小，中位数不是n/2就是n/2-1.
5.棋子排序
2n个棋子，其中n个为红棋，n个为黑棋，分别编号为（1~n）,给一个2n序列，需要让红黑棋相对自己的编号有序。
如BBRRBBRR 其中B为黑棋，R为红棋，对应编号为3，2，2，1，1，4，4，3 。要让B的编号相对有序1,2,3,4，R的编号相对有序1,2,3,4.
个人解法：贪心，每次找距离最小的逆序对，距离相等时找靠近编号0的。
全部评论
(0) 回帖