写点什么

架构一期第八周作业

用户头像
Airs
关注
发布于: 2020 年 11 月 15 日

作业一:

(至少完成一个)

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

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

伪代码:

class Node(object):
def __init__(self, data, address=None):
self.data = data
self.next = address
class LinkedList(object):
def __init__(self):
self.length = 0
self.head = None
# 向链表追加节点
def add(self, data):
if self.length:
node = self.head
while node.next:
node = node.next
else:
node.next = Node(data)
else:
self.head = Node(data)
self.length += 1
# 返回指定索引节点
def get(self, index):
if index >= self.length:
raise(IndexError, "list index out of range.")
node = self.head
while index:
node = node.next
index -= 1
return node
# 删除一个节点
def delete(self, index):
if index == 0:
self.head = self.head.next
elif index == self.length-1:
self.get(index-1).next = None
else:
self.get(index - 1).next = self.get(index+1)
self.length -= 1
# 在指定索引位置插入一个节点
def insert(self, index, data):
if index == 0:
self.add(data)
else:
node = Node(data, self.get(index))
self.get(index - 1).next = node
self.length += 1
# 遍历链表中的节点值
def traverse(self):
value = list()
node = self.head
while node:
value.append(node.data)
node = node.next
return value
# 遍历链表的节点中下一个节点的地址
def traverse_node(self):
node_list = list()
node = self.head
while node:
node_list.append(node.address)
node = node.next
return node_list
if __name__ == "__init__":
print("begin")
Om = LinkedList # 创建长度为m的链表
On = LinkedList # 创建长度为n的链表
node_Om = Om.traverse_node # 遍历节点中下一个节点的地址形成顺序列表
node_On = On.traverse_node # 遍历节点中下一个节点的地址形成顺序列表
for i in node_Om:
if node_Om[i] == node_On[i]: # 对比节点中下一个节点的地址
print("节点地址为" + str(i-1) + "的数据:" + Om[i-1] + "开始重合")
break
else:
print("两个链表中没有重合元素")
break

时间复杂度为:O(N)



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



作业二:

  • 根据当周学习情况,完成一篇学习总结



发布于: 2020 年 11 月 15 日阅读数: 27
用户头像

Airs

关注

Emmmmmmm 2018.02.28 加入

Emmmmmmm

评论

发布
暂无评论
架构一期第八周作业