架构师训练营第 8 周作业

 关注
发布于: 2020 年 07 月 26 日
作业一：单向链表相交问题假设这两个单向链表没有环
有两个单向链表（链表长度分别为m,n），这两个单向链表有可能在某个元素合并，如上图所示，也有可能不合并。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是途中的x元素。
请用（伪）代码描述算法，并给出时间复杂度和空间复杂度。
解答：
本题采用三种方法解决，第三种方法参考了LeetCode的解题方法（很NB），做算法题可以开拓自己的解决问题的思路。
暴力法：
a. 最容易想到的一种方法，也就是每一个节点进行比对，该方法不会开辟额外的空间存储中间节点，但是由于每个节点比对，相当于循环m*n次，时间复杂度相对较高。
b. 该方法时间复杂度是O(m∗n​)，空间复杂度是O(1​)；
Hash法：
a. 该方法将任意链表的节点遍历存储到Hash表中
b. 然后遍历另外一个链表节点，看是否在Hash表中存在，如果存在就是相交合并的节点
c. 如果遍历完成后，都没有相交节点，则两个链表无合并节点
该方法Hash表的快速查询特性，查询时间复杂度是O(1)，两个链表遍历的时间复杂度是O(m+n)，所以该方法的时间复杂度是O(m+n​)，由于使用了Hash表存储一个链表的节点，所以它的空间复杂度是O(m​)或者O(n​)。
双指针法：
a. 该方法参考了LeetCode上的解题方法，很巧妙，代码很简单，有时候并不是解题逻辑多么困难，而是思路少，也就是见识少、思考少，做算法题还是很有意思的
b. 该方法定义两个指针，分别指向两个链表的头节点，两个指针同时移动遍历并比较指向节点，当遍历到链表最后一个节点时指针指向另一个链表的头节点继续遍历比较，如果没有合并节点，则这两个指针的遍历次数就是两个链表的长度之和，即m+n，最后两个指针会指向nvl，指向相同退出循环
该方法两个链表的每个节点遍历一次，所以时间复杂度是O(m+n​)，空间复杂度是O(1​)
ListNode节点
public class ListNode {
    private static Map<String, ListNode> nodeStore = new HashMap<>();
    public String value;
    public ListNode next;
    public ListNode(String value) {
        this.value = value;
    }
    public static ListNode of(String[] array) {
        if (Optional.ofNullable(array).orElse(new String[0]).length != 0) {
            List<ListNode> nodes = Arrays.stream(array)
                    .map(ListNode::getListNode)
                    .collect(Collectors.toList());
            for (int i = 0; i < nodes.size() - 1; i++) {
                nodes.get(i).next = nodes.get(i + 1);
            }
            return nodes.get(0);
        }
        return null;
    }
    private static ListNode getListNode(String val) {
        return Optional.ofNullable(nodeStore.get(val))
                .orElseGet(() -> {
                    ListNode listNode = new ListNode(val);
                    nodeStore.put(val, listNode);
                    return listNode;
                });
    }
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        ListNode next = this;
        do {
            sb.append(next.value);
            next = next.next;
            if (next != null) {
                sb.append("->");
            }
        } while (next != null);
        sb.append("]");
        return sb.toString();
    }
}
暴力法：
/**
     * <strong>暴力比对法: </strong>以nodeA的一个节点与nodeB的每个节点比较，一轮比较完成后没有相同节点，则取nodeA的next节点再进行比较，直到找到相同节点或者全部比较未找到相同节点时退出<br/>
     * 该方法的时间复杂度是O(m*n)，空间复杂度是O(1)
     *
     * @param nodeA
     * @param nodeB
     * @return
     */
    public static ListNode firstMeetNode1(ListNode nodeA, ListNode nodeB) {
        if (nodeA == null || nodeB == null) {
            return null;
        }
        ListNode tempA = nodeA;
        ListNode tempB = nodeB;
        do {
            do {
                if (tempA == tempB) {
                    break;
                }
                tempB = tempB.next;
            } while (tempB != null);
            if (tempA == tempB) {
                break;
            }
            tempA = tempA.next;
            tempB = nodeB;
        } while (tempA != null);
        return tempA;
    }
Hash法：
    /**
     * <strong>Hash比对法： </strong>先将nodeA的所有节点放到一个集合中，然后再遍历nodeB节点看是否在集合中存在，如果存在则退出遍历循环，该节点即是nodeA与nodeB的相交节点<br/>
     * 该方法的时间复杂度是O(m+n)，由于使用了集合存储nodeA的节点，所以空间复杂度是O(m)或O(n)
     *
     * @param nodeA
     * @param nodeB
     * @return
     */
    public static ListNode firstMeetNode2(ListNode nodeA, ListNode nodeB) {
        if (nodeA == null || nodeB == null) {
            return null;
        }
        Set<ListNode> set = new HashSet<>();
        ListNode node = nodeA;
        set.add(node);
        while (node.next != null) {
            node = node.next;
            set.add(node);
        }
        node = nodeB;
        while (node != null && !set.contains(node)) {
            node = node.next;
        }
        return node;
    }
双指针法：
    /**
     * <strong>双指针法: </strong>该方法定义两个指针遍历一次两个链表，所以时间复杂度是O(m+n)，未开辟空间存取中间节点所以空间复杂度是O(1)
     * <ol>
     *     <li>定义两个指针，第一个指向nodeA，另一个指向nodeB，遍历节点</li>
     *     <li>当第一个遍历到nodeA的最后一个节点后然后指向nodeB继续遍历，另一个指针遍历到nodeB的最后一个节点时指向nodeA继续遍历</li>
     *     <li>当两个指针指向的节点相同时就退出，此时两个指针指向的节点就是nodeA与nodeB相交的节点</li>
     *     <li>如果遍历到最后都没有相交节点，则两个指针会指向null退出循环</li>
     * </ol>
     * 例如：有相交节点<br/>
     * nodeA：[a->b->x->y->z]<br/>
     * nodeB：[d->e->f->x->y->z]<br/>
     *
     * pA：[a->b->x->y->z->d->e->f->x->y->z]<br/>
     * pB：[d->e->f->x->y->z->a->b->x->y->z]<br/>
     *
     * pA和pB遍历到节点7时判断相同退出循环，返回节点7
     *
     * <hr/>
     *
     * 例如：无相交节点<br/>
     * nodeA：[d->e->f]<br/>
     * nodeB：[a->b->x->y->z]<br/>
     *
     * pA：[d->e->f->a->b->x->y->z->NVL]<br/>
     * pB：[a->b->x->y->z->d->e->f->NVL]<br/>
     *
     * 最终：pA == pB == NULL
     *
     * @param nodeA
     * @param nodeB
     * @return
     */
    public static ListNode firstMeetNode3(ListNode nodeA, ListNode nodeB) {
        if (nodeA == null || nodeB == null) {
            return null;
        }
        ListNode pa = nodeA;
        ListNode pb = nodeB;
        while (pa != pb) {
            pa = pa == null ? nodeB : pa.next;
            pb = pb == null ? nodeA : pb.next;
        }
        return pa;
    }
测试代码：
    public static void main(String[] args) {
        String[] arrayA = {"a", "b", "x", "y", "z"};
        ListNode nodeA = ListNode.of(arrayA);
        String[] arrayB = {"d", "e", "f", "x", "y" ,"z"};
        ListNode nodeB = ListNode.of(arrayB);
        System.out.println(nodeA);
        System.out.println(nodeB);
        System.out.println("暴力法："+ Test.firstMeetNode1(nodeA, nodeB));
        System.out.println("Hash法："+ Test.firstMeetNode2(nodeA, nodeB));
        System.out.println("双指针法："+ Test.firstMeetNode3(nodeA, nodeB));
    }
测试输出结果：
作业二：请画出DataNode服务器节点宕机的时候，HDFS的处理过程时序图
1. DataNode会在启动后向NameNode注册
2. DataNode每隔一段时间（3秒钟）向NameNode主动发送心跳，心跳会带着NameNode的命令
3. NameNode在超过一定时间（10分钟）未收到DataNode的心跳，就认为该DataNode出现问题
4. NameNode中存储着每个DataNode的文件块信息，NameNode找到该DataNode上的文件块信息及分布在哪些DataNode服务器上
5. NameNode向这些DataNode发送文件块复制命令，将文件块复制到指定的DataNode上
6. 当DataNode复制完成后，通知NameNode复制任务完成
发布于: 2020 年 07 月 26 日阅读数: 37
王友

 关注
懒是一种艺术 2018.03.26 加入
间歇性自律，持续性懒散，真的很懒！
发布
暂无评论