简介
我正在学习edX的课程,并且已经花了3个小时的时间来完成这个练习作业,但是我仍然找不到一种方法来实现这个方法,而不会花费太长的时间,并且会使自动分级机超时。
我尝试了3种不同的方法,都是做同样的事情,包括2种递归方法和1种非递归方法(我最新的)。
我认为我的代码存在的问题是,查找子节点的方法太长了,因为它必须遍历整个节点列表。
输入和输出格式
输入包括第一行上的N,其为第2行上给出的列表的大小。
- 范例:*
5
-1 0 4 0 3
若要从此生成树:数组中的每个值都是指向数组中另一个索引的指针,因此在上面的示例中,0是-1(索引0)的子节点。由于-1不指向其他索引,因此它是根节点。
范例中的树形结构具有根节点-1,它有两个子系0(索引1)和0(索引3)。索引1的0没有子系,索引3的0有1个子系:3(索引4),而该子节点又只有一个子节点4(索引2)。
上述输入产生的输出为4。这是因为包含-1(根节点)、0、3和4的分支的最大高度为4,而另一个分支(-1和0)的高度为2。
如果你需要更详细的解释,那么我可以在评论中再给予一个例子!
输出是树的最大高度。输入的大小达到了100,000这是我遇到的麻烦,因为它必须在正好3秒或低于的时间内完成。
我的代码
这是我最新的非递归方法,我认为这是我做的最快的方法(仍然不够快)。我使用了网站上的启动程序,我也会在我的代码下面包括它。无论如何,谢谢你的帮助!
我的代码:
# python3
import sys, threading
sys.setrecursionlimit(10**7) # max depth of recursion
threading.stack_size(2**27) # new thread will get stack of such size
def height(node, parent_list):
h = 0
while not node == -1:
h = h + 1
node = parent_list[node]
return h + 1
def search_bottom_nodes(parent_list):
bottom_nodes = []
for index, value in enumerate(parent_list):
children = [i for i, x in enumerate(parent_list) if x == index]
if len(children) == 0:
bottom_nodes.append(value)
return bottom_nodes
class TreeHeight:
def read(self):
self.n = int(sys.stdin.readline())
self.parent = list(map(int, sys.stdin.readline().split()))
def compute_height(self):
# Replace this code with a faster implementation
bottom_nodes = search_bottom_nodes(self.parent)
h = 0
for index, value in enumerate(bottom_nodes):
h = max(height(value, self.parent), h)
return h
def main():
tree = TreeHeight()
tree.read()
print(tree.compute_height())
threading.Thread(target=main).start()
edX启动器:
# python3
import sys, threading
sys.setrecursionlimit(10**7) # max depth of recursion
threading.stack_size(2**27) # new thread will get stack of such size
class TreeHeight:
def read(self):
self.n = int(sys.stdin.readline())
self.parent = list(map(int, sys.stdin.readline().split()))
def compute_height(self):
# Replace this code with a faster implementation
maxHeight = 0
for vertex in range(self.n):
height = 0
i = vertex
while i != -1:
height += 1
i = self.parent[i]
maxHeight = max(maxHeight, height);
return maxHeight;
def main():
tree = TreeHeight()
tree.read()
print(tree.compute_height())
threading.Thread(target=main).start()
1条答案
按热度按时间ejk8hzay1#
只需缓存先前计算的dict中遍历过的节点的高度,并在将它们作为父节点引用时重用它们。
假设您的问题输入相同,此代码(以及您的原始代码)将输出: