架构师训练营 - 第八周 - 作业一

关注
发布于: 2020 年 11 月 15 日
作业1题目有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，也可能不合并，如下图所示的这样。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。
请用代码（或伪代码）描述算法，并给出时间复杂度。
解答解答1使用Set集合判断元素是否已经加入集合，如果第一次发现重复元素，则代表该元素为第一个合并元素。
    public static String method1(Node node1, Node node2) {
        if (node1 == null || node2 == null) {
            return null;
        }
        Set<String> nodes = new HashSet<>();
        while (node1 != null) {
            nodes.add(node1.value);
            node1 = node1.next;
        }
        while (node2 != null) {
            if (nodes.contains(node2.value)) {
                return node2.value;
            }
            node2 = node2.next;
        }
        return null;
    }
时间复杂度: 遍历2个链表(n m)，O(n+m)=O(n)
空间复杂度: 需要开辟额外存储空间存储Set集合，O(n+m)=O(n)
解答2对单链表首尾倒置，然后判断从首节点开始判断，直到找到第一个不相同的元素，那么该元素前一个节点即为第一个合并元素。
    public static String method2(Node node1, Node node2) {
        if (node1 == null || node2 == null) {
            return null;
        }
        node1 = revertNode(node1);
        node2 = revertNode(node2);
        String result = null;
        while (node1.value.equals(node2.value)) {
            result = node1.value;
            node1 = node1.next;
            node2 = node2.next;
        }
        return result;
    }
    public static Node revertNode(Node node) {
        if (node == null) {
            return null;
        }
        Node tempNode = new Node(null, null);
        tempNode.next = node;
        Node prev = tempNode.next;
        Node pCur = prev.next;
        while (pCur != null) {
            prev.next = pCur.next;
            pCur.next = tempNode.next;
            tempNode.next = pCur;
            pCur = prev.next;
        }
        return tempNode.next;
    }
时间复杂度: 遍历2个链表(n m)，O(n+m)=O(n)
空间复杂度: O(1)
测试代码
    public static void main(String[] args) {
        // node1 a - b - x - y - z
        Node node1 = new Node("a", new Node("b", new Node("x", new Node("y", new Node("z", null)))));
        // node2 d - e - f - x - y - z
        Node node2 = new Node("d", new Node("e", new Node("f", new Node("x", new Node("y", new Node("z", null))))));
        System.out.println("x".equals(method1(node1, node2)));
        System.out.println("x".equals(method2(node1, node2)));
        // node1 a - b - x
        Node node3 = new Node("a", new Node("b", new Node("x", null)));
        // node2 d - e - f - y - z
        Node node4 = new Node("d", new Node("e", new Node("f", new Node("y", new Node("z", null)))));
        System.out.println(method1(node3, node4) == null);
        System.out.println(method2(node3, node4) == null);
    }
    
        static class Node {
        String value;
        Node next;
        public Node(String value, Node next) {
            this.value = value;
            this.next = next;
        }
    }
作业2题目请画出 DataNode 服务器节点宕机的时候，HDFS 的处理过程时序图。
解答DataNode是存储数据的节点，当节点失效时，NameNode节点会发现心跳失败，开始执行数据迁移操作，找到失效节点上数据存储信息，然后向对应存储节点发送复制命令，存储节点收到命令之后复制指定数据到其他节点上。
时序图如下:
﻿
发布于: 2020 年 11 月 15 日阅读数: 26
行者

关注
还未添加个人签名 2018.03.09 加入
还未添加个人简介
发布
暂无评论
创作场景

架构师训练营 - 第八周 - 作业一

作业1

题目

解答

解答1

解答2

测试代码

作业2

题目

解答

行者

评论
