写点什么

架构师训练营 1 期第 8 周:性能优化(二)- 作业

用户头像
piercebn
关注
发布于: 2020 年 11 月 15 日

一、有两个单向链表(链表长度分别为 m,n),这两个单向链表有可能在某个元素合并,也可能不合并,如下图所示的这样。现在给定两个链表的头指针,在不修改链表的情况下,如何快速地判断这两个链表是否合并?如果合并,找到合并的元素,也就是图中的 x 元素。 请用代码(或伪代码)描述算法,并给出时间复杂度。

解题思路:

如果两个没有环的链表相交于某一节点,那么在这个节点之后的所有节点都是两个链表共有的,则最后一个节点也一定是共有的。那么,我们只要判断两个链表的尾指针是否相等即可。如果相等,则链表相交;否则,链表不相交。时间复杂度为O(Length1+ Length2),也就是线性O(N)。

代码实现:

public class FindCrossNode {

public static class Node {
public int data;
public Node next;

public Node(int data) {
this.data = data;
}
}

public static Node findNode(Node head1, Node head2) {

if(head1 == null || head2 == null) {
return null;
}

Node p1 = head1;
Node p2 = head2;
int len1 = 0;
int len2 = 0;
int diff = 0;

//遍历链表1
System.out.println("单向链表1:");
while (p1.next != null) {
System.out.print(p1.data + "->");
p1 = p1.next;
len1++;
}
len1++;
System.out.println(p1.data);
System.out.println("链表1长度:" + len1);

//遍历链表2
System.out.println("单向链表2:");
while (p2.next != null) {
System.out.print(p2.data + "->");
p2 = p2.next;
len2++;
}
len2++;
System.out.println(p2.data);
System.out.println("链表2长度:" + len2);

//两个链表尾节点不相等,代表两个链表没有合并
if(p1 != p2) {
return null;
}

//找到两个链表的合并节点,并返回合并节点
diff = Math.abs(len1-len2);

p1 = (len1 > len2)?head1:head2;
p2 = (len1 > len2)?head2:head1;

for (int i=0; i<diff; i++) {
p1 = p1.next;
}

while (p1 != p2) {
p1 = p1.next;
p2 = p2.next;
}

return p1;
}

public static void main(String[] args) {
//初始化节点
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
Node node6 = new Node(6);
Node node7 = new Node(7);
Node node8 = new Node(8);
Node node9 = new Node(9);
Node node10 = new Node(10);

//构建链表
node1.next = node2;
node2.next = node3;
node3.next = node8;

node4.next = node5;
node5.next = node6;
node6.next = node7;
node7.next = node8;

node8.next = node9;
node9.next = node10;

//找到合并节点
Node node = findNode(node1, node4);
System.out.println("合并节点元素值为:"+node.data);
}
}

结果输出:

单向链表1:
1->2->3->8->9->10
链表1长度:6
单向链表2:
4->5->6->7->8->9->10
链表2长度:7
合并节点元素值为:8

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

涉及角色:

NameNode,DataNode1,DataNode2,DataNode3,DataNode4

处理过程:

假设DataNode1,DataNode2,DataNode3存储了一份数据的三份复制,当DataNode1宕机的时候,NameNode会检测出来丢失的数据块,并给DataNode2和DataNode3发送指令,将丢失的数据块复制到DataNode4。具体处理过程参看下图:



发布于: 2020 年 11 月 15 日阅读数: 23
用户头像

piercebn

关注

还未添加个人签名 2019.07.24 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营 1 期第 8 周:性能优化(二)- 作业