帆软后端笔试（9.10~9.13）
下午参加了帆软后端的笔试，其中包含6道单选，4道多选，5道逻辑填空题，以及一道算法题。总体感觉偏难，以下印象比较深的一道逻辑题及算法题进行介绍。
-
有一道逻辑题比较有意思，大意是存在1000份水与1份无色试剂，提供若干可与该试剂反应的试纸，每次反应的时间为20分钟，如果需要在1个小时内找出该试剂，大致需要多少张试纸？
提示：每张试纸可以滴不受数量限制的样品，滴样品时间不受限制。
这道题分析有点类似于二分查找，但由于反应时间的限制，相对更加复杂，后来想想这点没分析好，填的结果并不对。。。
-
另一道是算法题：假设有n个链表，每个链表长度的不一，链表中每个的节点包含key与value。不同链表比较时，如果key值相同，则value相加，题目目标是将n个无序链表转化为单个有序链表。
链表数目 n与单个链表长度k1, k2, ..., kn,及每个节点信息需要通过控制台扫描输入，控制台中的节点形式为 1:2，因此需要对此字符串解析。这道题糅合了控制台输入解析，链表排序，链表合并，如果单个链表长度为50万到100万时，需要考虑如何优化链表排序与链表合并。
最开始打算 key与value保存在hashmap, 但感觉由hashmap构造链表不合适，其实节点类定义key与value也可以解决问题，这道题感觉还是挺难的，没a出来。。。
下面是提交后写的答案，参考了链表排序（leetcode 148）与合并k个升序链表（leetcode 23）
public class SortLinkedListDemo {
/*测试用例依次为 链表数目为3 单个链表长度分别为2、3、4，以及每个节点长度
3 2 3 4
1:2 2:3
3:4 2:7 4:3
7:3 9:1 4:3 12:2*/
public static void main(String[] args) throws IOException {
ListNode[] listNodes = scannrValue();
for (int i = 0; i < listNodes.length; i++) {
listNodes[i]=sortSingleList(listNodes[i]);
}
ListNode head = mergeKLists(listNodes);
//输出检验
int count = 0;
while (head != null) {
System.out.println("count: " + (++count) + " key: " + head.key + " val: " + head.val);
head = head.next;
}
}
//扫描输入
private static ListNode[] scannrValue() {
Scanner sc = new Scanner(System.in);
int linkedListNum = sc.nextInt();//链表数目
int[] linkedListLength = new int[linkedListNum];
for (int i = 0; i < linkedListNum; i++) {
//保存每个链表长度
linkedListLength[i] = sc.nextInt();
}
//节点解析，并将每个链表头结点保存在ListNode[]数组中
ListNode[] listNodes = new ListNode[linkedListNum];
for (int i = 0; i < linkedListNum; i++) {
ListNode dummy = new ListNode(0, 0);
ListNode cur = dummy;
dummy.next = cur;
for (int j = 0; j < linkedListLength[i]; j++) {
//节点解析
String[] str = sc.next().split(":");
ListNode temp = new ListNode(Integer.parseInt(str[0]), Integer.parseInt(str[1]));
cur.next = temp;
cur = temp;
}
//添加头结点
listNodes[i] = dummy.next;
}
return listNodes;
}
//采用归并进行链表排序
public static ListNode sortSingleList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode slow = head, fast = head, pre = head;
while (fast != null && fast.next != null) {
pre = slow;//这两步顺序很重要
slow = slow.next;
fast = fast.next.next;
}
pre.next = null;
return merge(sortSingleList(head), sortSingleList(slow));
}
//输入两个链表头节点，返回合并后头节点
private static ListNode merge(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
ListNode cur = null;
if (l1.key == l2.key) {
l1.next = merge(l1.next, l2.next);
l1.val +=l2.val;
cur = l1;
}
if (l1.key < l2.key) {
l1.next = merge(l1.next, l2);
cur = l1;
}
if (l1.key > l2.key) {
l2.next = merge(l1, l2.next);
cur = l2;
}
return cur;
}
//n个链表合并
public static ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) return null;
if (lists.length == 1) return lists[0];
if (lists.length == 2) return merge(lists[0], lists[1]);
return merge(mergeKLists(Arrays.copyOfRange(lists, 0, lists.length / 2)),
mergeKLists(Arrays.copyOfRange(lists, lists.length / 2, lists.length)));
}
//节点定义
static class ListNode {
//模拟包含键值对类型链表
private int key;
private int val;
private ListNode next;
public ListNode(int key, int val) {
this.key = key;
this.val = val;
}
}
}
