架构师训练营 - 性能优化 2

用户头像
Pontus
关注
发布于: 2020 年 07 月 28 日

作业一

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

参考

作业二

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

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





时空间复杂度见程序中备注。

//https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
package y_linkedlist_intersection
import (
"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
}



用户头像

Pontus

关注

还未添加个人签名 2018.04.21 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营 - 性能优化2