极客时间架构师训练营 - week8 - 作业 1
发布于: 2020 年 07 月 29 日
有两个单向链表(链表长度分别为 m,n),这两个单向链表有可能在某个元素合并,如下图所示的这样,也可能不合并。现在给定两个链表的头指针,在不修改链表的情况下,如何快速地判断这两个链表是否合并?如果合并,找到合并的元素,也就是图中的 x 元素。
请用(伪)代码描述算法,并给出时间复杂度和空间复杂度。
思路:将其中的一个链表全部存入哈希表,然后遍历另外一个链表,如果之前的链表包含此元素,记录下此时位置,即可以判断两个链表存在合并的元素X。
package jjn;import java.util.Objects;import java.util.StringJoiner;/** * @author Jiang Jining * @date 2020/7/29 21:54 */public class Node { private Integer index; private String value; public Node() { } public Integer getIndex() { return index; } public void setIndex(Integer index) { this.index = index; } public String getValue() { return value; } public void setValue(String value) { this.value = value; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Node node = (Node) o; return Objects.equals(value, node.value); } @Override public int hashCode() { return Objects.hash(value); } @Override public String toString() { return new StringJoiner(", ", Node.class.getSimpleName() + "[", "]") .add("index=" + index) .add("value='" + value + "'") .toString(); }}
package jjn;import java.util.*;/** * @author Jiang Jining * @date 2020/7/29 21:54 */public class LinkListTest { public static void main(String[] args) { List<Node> listA = new LinkedList<>(); List<Node> listB = new LinkedList<>(); for (int i = 0; i < 10; i++) { Node randomNode = getRandomNode(i); listA.add(randomNode); } for (int i = 0; i < 15; i++) { Node randomNode = getRandomNode(i); listB.add(randomNode); } System.out.println("listA:"); listA.forEach(System.out::println); System.out.println("listB:"); listB.forEach(System.out::println); Node mergingNode = getMergingNode(listA, listB); if (mergingNode == null) { System.out.println("两个链表无合并"); } else { System.out.println("合并的元素是:" + mergingNode); } } private static Node getRandomNode(int index) { Node node = new Node(); node.setIndex(index); node.setValue((char) (Math.random() * 26 + 'A') + ""); return node; } private static Node getMergingNode(List<Node> listA, List<Node> listB) { if (listA == null || listB == null) { return null; } Set<Node> nodes = new HashSet<>(listA.size()); nodes.addAll(listA); for (Node node : listB) { if (nodes.contains(node)) { return node; } } return null; }}
请画出 DataNode 服务器节点宕机的时候,HDFS 的处理过程时序图。
划线
评论
复制
发布于: 2020 年 07 月 29 日阅读数: 44
版权声明: 本文为 InfoQ 作者【jjn0703】的原创文章。
原文链接:【http://xie.infoq.cn/article/c018e67cb2dc9e07a6e71c8cb】。
本文遵守【CC-BY 4.0】协议,转载请保留原文出处及本版权声明。
jjn0703
关注
Java工程师/终身学习者 2018.03.26 加入
USTC硕士/健身健美爱好者/Java工程师.
评论