首页 > 帆软后端笔试(9.10~9.13)
头像
木有offer
编辑于 2020-09-14 12:05
+ 关注

帆软后端笔试(9.10~9.13)

下午参加了帆软后端的笔试,其中包含6道单选,4道多选,5道逻辑填空题,以及一道算法题。总体感觉偏难,以下印象比较深的一道逻辑题及算法题进行介绍。

  1. 有一道逻辑题比较有意思,大意是存在1000份水与1份无色试剂,提供若干可与该试剂反应的试纸,每次反应的时间为20分钟,如果需要在1个小时内找出该试剂,大致需要多少张试纸?

提示:每张试纸可以滴不受数量限制的样品,滴样品时间不受限制。

这道题分析有点类似于二分查找,但由于反应时间的限制,相对更加复杂,后来想想这点没分析好,填的结果并不对。。。

  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;
		}
	}
}


全部评论

(5) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐