架构师训练营 Week8 - 课后作业

用户头像
关注
发布于: 2020 年 12 月 15 日
架构师训练营 Week8 - 课后作业

作业一

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

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

解答:

  • 如果不考虑空间限制的情况下可以是O(m+n) 也就是O(n)。最差用两个互相遍历O(m*n)。

图例m=5, n=6 也就是 O(m+n)<= 5+6, 最差互相遍历O(m*n) <= 5*6

  • 空间换时间算法O(n), 这里用HashMap替代构建Hash算法的过程

package io.radon.w8;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
Main instance = new Main();
LinkedList<String> m = new LinkedList<String>();
m.addAll(Arrays.asList(new String[] {"a","b","x","y","z"}));
LinkedList<String> n = new LinkedList<String>();
n.addAll(Arrays.asList(new String[] {"d","e","f","x","y","z"}));
boolean isMerged = instance.isMerged(m, n);
System.out.printf("is Merged : %s \n", isMerged );
}
boolean isMerged(LinkedList<String> m, LinkedList<String> n) {
HashMap<String,String> map = new HashMap<String, String>();
int step = 0;
boolean result = false;
if (m.size() > n.size()) {
for (String temp: m) {
System.out.printf("step: %s \n",++step);
map.put(temp,null);
}
for (String temp: n) {
System.out.printf("step: %s \n",++step);
if(map.containsKey(temp)) {
result = true;
break;
}
}
} else {
for (String temp: n) {
System.out.printf("step: %s \n",++step);
map.put(temp,null);
}
for (String temp: m) {
System.out.printf("step: %s \n",++step);
if(map.containsKey(temp)) {
result = true;
break;
}
}
}
System.out.printf("m.length: %s, n.length: %s, final step: %s\n",m.size(), n.size(), step);
return result;
}
}
Output:
step: 1
step: 2
step: 3
step: 4
step: 5
step: 6
step: 7
step: 8
step: 9
m.length: 5, n.length: 6, final step: 9
is Merged : true



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

--空--



用户头像

关注

还未添加个人签名 2018.09.18 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营 Week8 - 课后作业