架构师训练营 - 性能优化 2
发布于: 2020 年 07 月 28 日
作业一
请画出 DataNode 服务器节点宕机的时候,HDFS 的处理过程时序图。
作业二
有两个单向链表(链表长度分别为 m,n),这两个单向链表有可能在某个元素合并,如下图所示的这样,也可能不合并。现在给定两个链表的头指针,在不修改链表的情况下,如何快速地判断这两个链表是否合并?如果合并,找到合并的元素,也就是图中的 x 元素。
请用(伪)代码描述算法,并给出时间复杂度和空间复杂度。
时空间复杂度见程序中备注。
//https://leetcode-cn.com/problems/intersection-of-two-linked-lists/package y_linkedlist_intersectionimport ( "github.com/stretchr/testify/assert" "testing")//程序尽量满足 O(n) 时间复杂度,且仅用 O(1) 内存。func TestListIntersection(t *testing.T) { a := &ListNode{1, nil} b := &ListNode{1, nil} d := &ListNode{1, nil} e := &ListNode{1, nil} f := &ListNode{1, nil} x := &ListNode{2, nil} y := &ListNode{1, nil} z := &ListNode{1, nil} a.Next = b b.Next = x d.Next = e e.Next = f f.Next = x x.Next = y y.Next = z assert.Equal(t, x, getIntersectionNode(a, d))}type ListNode struct { Val int Next *ListNode}func getIntersectionNode(headA, headB *ListNode) *ListNode { return getIntersectionNode3(headA, headB)}//方法1:遍历找到较长链表,然后长链表先遍历到同样起始位置,再一起遍历//O(2(m+n)), O(1)func getIntersectionNode1(headA, headB *ListNode) *ListNode { if headA == nil || headB == nil { return nil } getListLength := func(head *ListNode) int { length := 0 for head != nil { length++ head = head.Next } return length } m := getListLength(headA) n := getListLength(headB) if m > n { for i := m - n; i > 0; i-- { headA = headA.Next } } if m < n { for i := n - m; i > 0; i-- { headB = headB.Next } } for headA != nil { if headA == headB { return headA } headA, headB = headA.Next, headB.Next } return nil}//方法2:将一个链表的node存入hashmap,遍历另一个链表,O(1)的时间复杂度去对比//O(m+n),O(n or m)func getIntersectionNode2(headA, headB *ListNode) *ListNode { hash := make(map[*ListNode]int) for ; headA != nil; headA = headA.Next { hash[headA] = 1 } for ; headB != nil; headB = headB.Next { if _, ok := hash[headB]; ok { return headB } } return nil}//方法3:将链表反转,然后从头开始遍历,找到第一个不相等的node后,再反转回来 - O(2(m+n)+n)//方法3:将链表放入两个栈中,然后出栈,找到第一个不相等的node后,把上一个node返回 - O(m+n), O(m+n)//有点复杂,就不写了//方法4://假设相交部分长度为c, headA不相交部分为a,headB不相交部分为b//headA先遍历完之后,再从headB的头开始遍历,长度为a+c+b//headB同样的操作,长度为b+c+a//第一次相等的时候,就是相交点node//如果链表不相交,则最终curA==curB==nil,也可直接返回//O(m+n), O(1)func getIntersectionNode3(headA, headB *ListNode) *ListNode { curA, curB := headA, headB for curA != curB { if curA == nil { curA = headB } else { curA = curA.Next } if curB == nil { curB = headA } else { curB = curB.Next } } return curA}
划线
评论
复制
发布于: 2020 年 07 月 28 日阅读数: 56
Pontus
关注
还未添加个人签名 2018.04.21 加入
还未添加个人简介
评论