架构师训练营 -week8- 作业

用户头像
晓-Michelle
关注
发布于: 2020 年 07 月 26 日
架构师训练营-week8-作业

第一题:

判断是否合并的方法:

本文采取了将其中一个链首尾相连,通过快慢指针查另一个链中是否存在环的方式进行判断。

找到合并的元素:

在网上找了些资料,依据以下结论完成代码。

已知头节点d到连接点x需要a步,环长度为L,快指针的前进步数是慢指针的2倍,快指针与慢指针相遇的节点为y。慢指针进入环中时,即慢指针在连接点x,此时快指针在b点,快指针需要2m步才能追上慢指针。设慢指针走了s步到相遇节点,快指针走了2s步到相遇节点。

可知,s=a+m;2s = a+n*L+m。

可得a=n*L-m,即若在头节点前置节点与相遇节点各设一指针,同时单步前进,则最后一定相遇在连接点x。

由于头节点的前置节点是虚空,所以修正为若在头节点与相遇节点的下一节点各设一指针,同时单步前进,则最后一定相遇在连接点x。

代码

节点Node<T>

package week8;
public class Node<T> {
Node<T> next;
T data;
public Node(T data) {
this.data = data;
this.next = null;
}
@Override
public String toString() {
// TODO Auto-generated method stub
StringBuilder sBuilder = new StringBuilder();
sBuilder.append(this.data);
return sBuilder.toString();
}
}

自定义链表接口IMyList<T>

package week8;
public interface IMyList<T> {
public void addNode(Node<T> node, int index);
public void addLast(T data);
public void addLast(Node<T> node);
public int getSize();
public void convertToRing();
}

自定义链表实现类MyList<T>

package week8;
import java.awt.event.MouseWheelEvent;
public class MyList<T> implements IMyList<T> {
Node<T> head;
int size;
public MyList(Node<T> node) {
// TODO Auto-generated constructor stub
this.head = node;
this.size = 1;
}
@Override
public void addLast(T data) {
// TODO Auto-generated method stub
this.addNode(new Node<T>(data), size);
}
public void addLast(Node<T> node) {
// TODO Auto-generated method stub
addNode(node, size);
}
public void addNode(T data, int index) {
if (index < 0 || index > size) {
return;
}
this.addNode(new Node<T>(data), index);
}
public void addNode(Node<T> node, int index) {
Node<T> preNode = this.head;
for (int i = 0; i < index - 1; i++) {
preNode = preNode.next;
}
node.next = preNode.next;
preNode.next = node;
this.size++;
}
@Override
public void convertToRing() {
Node<T> node = this.head;
for (int i = 0; i < this.size - 1; i++) {
node = node.next;
}
node.next = this.head;
}
@Override
public String toString() {
// TODO Auto-generated method stub
StringBuilder sBuilder = new StringBuilder();
sBuilder.append("size:" + this.size + "\r\n");
Node<T> tempNode = this.head;
sBuilder.append(tempNode.data.toString());
for (int i = 0; i < this.size - 1; i++) {
tempNode = tempNode.next;
sBuilder.append("->" + tempNode.data.toString());
}
return sBuilder.toString();
}
}

环工具类MyRing

package week8;
import java.util.HashMap;
import java.util.Map;
public class MyRing {
public static <T> boolean existHoop(MyList<T> list) {
if (list.size < 2) {
return false;
}
Node<T> fastNode = list.head.next;
Node<T> slowNode = list.head;
while (slowNode != null && fastNode != null) {
if (slowNode == fastNode) {
// System.out.println(slowNode.toString());
return true;
}
fastNode = fastNode.next.next;
slowNode = slowNode.next;
}
return false;
}
public static <T> Node<T> getRingHead(MyList<T> list) {
if (list.size < 2) {
return null;
}
Node<T> fastNode = list.head.next;
Node<T> slowNode = list.head;
while (slowNode != null && fastNode != null) {
if (slowNode == fastNode) {
break;
}
fastNode = fastNode.next.next;
slowNode = slowNode.next;
}
slowNode = list.head;
fastNode = fastNode.next;
while (slowNode != fastNode) {
slowNode = slowNode.next;
fastNode = fastNode.next;
}
return slowNode;
}
}

测试类MyListTest

package week8;
import junit.framework.TestCase;
public class MyListTest extends TestCase {
private MyList<String> listA;
private MyList<String> listB;
@Override
protected void setUp() {
// init node
Node<String> a = new Node<>("a");
Node<String> b = new Node<>("b");
Node<String> d = new Node<>("d");
Node<String> e = new Node<>("e");
Node<String> f = new Node<>("f");
Node<String> x = new Node<>("x");
Node<String> y = new Node<>("y");
Node<String> z = new Node<>("z");
// init listA
listA = new MyList<>(a);
listA.addLast(b);
listA.addLast(x);
listA.addLast(y);
listA.addLast(z);
// init listB
listB = new MyList<>(d);
listB.addLast(e);
listB.addLast(f);
listB.addLast(x);
listB.addLast(y);
listB.addLast(z);
}
public void testMyList() {
System.out.println("listA:"+listA.toString()+"\r\n");
System.out.println("listB:"+listB.toString()+"\r\n");
listA.convertToRing();
boolean hasHoop = MyRing.existHoop(listB);
if (hasHoop) {
Node<String> node = MyRing.getRingHead(listB);
System.out.println("存在合并元素,合并点为:"+node.toString());
}
}
}

结果输出:

时间复杂度:O(nlog n),空间复杂度:O(1)。

更正:时间复杂度O(N)

第二题:



DataNode失效时的过程:

DataNode启动时,会到NameNode注册,此后会定时发送心跳包给NameNode。当NameNode超时没有收到心跳包,则判定该DataNode失效。此时NameNode就会通过检查元数据找到失效的DataNode上备份数据块在哪些DataNode上。检查完成后,通知所有的服务器将失效DataNode上的数据块的备份复制到指定机器上。



发布于: 2020 年 07 月 26 日 阅读数: 45
用户头像

晓-Michelle

关注

还未添加个人签名 2020.05.30 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营-week8-作业