写点什么

架构师训练营第八周作业

用户头像
李日盛
关注
发布于: 2020 年 12 月 11 日

问题一

有两个单向链表(链表长度分别为m,n),这两个单向链表有可能在某个元素合并,也

可能不合并,如下图所示的这样。现在给定两个链表的头指针,在不修改链表的情况下,

如何快速地判断这两个链表是否合并?如果合并,找到合并的元素,也就是图中的 x 元

素。

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





解答:

  1. 最直观的搞法是两次for循环,时间复杂度为O(mn):

for(Object a: listA){
for(Object b: listB){
if(a.equals(b)){
return a;
}
}
}
  1. 根据题目分析,单向链表的特征是,单个元素后面只有一个指向,也就是说,如果两个链表是有相同的元素,那么从这个元素开始,后面所有的数据都是一样的。根据这个特点,我们可以通过只判断min(m,n)个元素就可以得出结论。这个算法的时间复杂度就是O(n)

int m = listA.size();
int n = listB.size();
int start = abs(m-n);
if(m > n){
for(int i=0;i<listB;i++){
if(listB.get(i).equals(listA.get(start+i))){
return listB.get(i);
}
}
}else{
for(int i=0;i<listA;i++){
if(listA.get(i).equals(listB.get(start+i))){
return listA.get(i);
}
}
}



问题二

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



解答



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

李日盛

关注

好架构=低成本+可实现 2018.01.22 加入

还未添加个人简介

评论

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