写点什么

【架构师训练营 1 期】第八周作业

用户头像
诺乐
关注
发布于: 2020 年 11 月 16 日

作业一:

有两个单向链表(链表长度分别为 m,n),这两个单向链表有可能在某个元素合并,也可能不合并,如下图所示的这样。现在给定两个链表的头指针,在不修改链表的情况下,如何快速地判断这两个链表是否合并?如果合并,找到合并的元素,也就是图中的 x 元素。

请用代码(或伪代码)描述算法,并给出时间复杂度。





解题思路:两个链表同时从头部往下查找(递归),经过每一层时分别记录两个链表的层节点,当链表1(或链表2)的子节点首次出现在链表2(或链表1)的历史节点里时,即该节点为第一个合并节点。




import java.util.HashMap;
import java.util.Map;

class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public class ListNodeDemo {

private final Map<ListNode, Integer> temp1 = new HashMap<>();
private final Map<ListNode, Integer> temp2 = new HashMap<>();

// 思路:两个链表同时从头部往下查找,经过每一层时分别记录两个链表的层节点,
// 当链表1(或链表2)的子节点首次出现在链表2(或链表1)的历史节点里时,即该节点为第一个合并节点。
public Integer getMergeVal(ListNode l1, ListNode l2) {
if (null == l1 && null == l2) return null;

if (null != l1) {
if (null != temp2.get(l1)) return l1.val;
temp1.put(l1, 1);
}

if (null != l2) {
if (null != temp1.get(l2)) return l2.val;
temp2.put(l2, 1);
}

return getMergeVal(
null != l1 ? l1.next : null,
null != l2 ? l2.next : null);
}

public static void main(String[] args) {
// 合并节点
ListNode merge_3 = new ListNode(555, null);
ListNode merge_2 = new ListNode(444, merge_3);
ListNode merge_1 = new ListNode(333, merge_2);

// 链表1
ListNode l1_3 = new ListNode(1111, merge_1);
ListNode l1_2 = new ListNode(111, l1_3);
ListNode l1_1 = new ListNode(11, l1_2);
ListNode l1 = new ListNode(1, l1_1); // 链表1头指针

// 链表2
ListNode l2_2 = new ListNode(222, merge_1);
ListNode l2_1 = new ListNode(22, l2_2);
ListNode l2 = new ListNode(2, l2_1); // 链表2头指针

Integer result = new ListNodeDemo().getMergeVal(l1_1, l2_1);
System.out.println("预期结果:" + merge_1.val);
System.out.println("最终结果:" + result);
}
}






该算法时间复杂度为O(n),其中n代表最长那条链表的长度。



作业二:

请画出 DataNode 服务器节点宕机的时候,HDFS 的处理过程时序图。





用户头像

诺乐

关注

还未添加个人签名 2018.12.01 加入

还未添加个人简介

评论

发布
暂无评论
【架构师训练营 1 期】第八周作业