从最后一个让步对象中寻找元素而不是值(Finding element from last yielding object instead of value)

我在课堂上遇到一个复杂的问题，问题是：

在单个链接列表中查找元素，该元素来自末尾的m个元素。

按照一些指南和阅读StackOverflow上的问题，我能够得到以下代码：

# Provided Node Class. class Node: def __init__(self, data): self.data = data self.next = None # Singly Linked List class SinglyLinkedList: # Initiate current object as start of list. def __init__(self): self.head = None # Add new node to list at currect position. def add(self, new_data): node = Node(new_data) node.next = self.head self.head = node # Set head as starting point and walk through list. def Question5(self, index): walk = self.head while walk is not None: yield walk.data walk = walk.next sll = SinglyLinkedList() sll.add(1); sll.add(4); sll.add(3); sll.add(8); sll.add(1); print ("Value at 4 is :", sll.Question5(4)) # ('Value at 4 is :', 1) sll.add(0); sll.add(0); sll.add(0); sll.add(0); sll.add(0); print ("Value at 0 is :", sll.Question5(0)) # ('Value at 0 is :', 0) sll.add(22345643); sll.add(12345643); sll.add(14375643); sll.add(12345633); sll.add(12345647); print ("Value at 12345643 is :", sll.Question5(12345643)) # ('Value at 12345643 is :', None)

然而，而不是我的输出是我期望它是我的代码显示运行时：

('Value at 4 is :', <generator object Question5 at 0x7f9635bb3870>) ('Value at 0 is :', <generator object Question5 at 0x7f9635bb3870>) ('Value at 12345643 is :', <generator object Question5 at 0x7f9635bb3870>)

有谁知道我在这种情况下做错了什么？谢谢。

I'm having a complex issue here with one of my questions for class, the question is:

Find the element in a singly linked list that's m elements from the end.

Following a few guides and reading questions on StackOverflow I was able to come up with the following code:

# Provided Node Class. class Node: def __init__(self, data): self.data = data self.next = None # Singly Linked List class SinglyLinkedList: # Initiate current object as start of list. def __init__(self): self.head = None # Add new node to list at currect position. def add(self, new_data): node = Node(new_data) node.next = self.head self.head = node # Set head as starting point and walk through list. def Question5(self, index): walk = self.head while walk is not None: yield walk.data walk = walk.next sll = SinglyLinkedList() sll.add(1); sll.add(4); sll.add(3); sll.add(8); sll.add(1); print ("Value at 4 is :", sll.Question5(4)) # ('Value at 4 is :', 1) sll.add(0); sll.add(0); sll.add(0); sll.add(0); sll.add(0); print ("Value at 0 is :", sll.Question5(0)) # ('Value at 0 is :', 0) sll.add(22345643); sll.add(12345643); sll.add(14375643); sll.add(12345633); sll.add(12345647); print ("Value at 12345643 is :", sll.Question5(12345643)) # ('Value at 12345643 is :', None)

However instead of my output being what I expect it to be my code shows this when ran:

('Value at 4 is :', <generator object Question5 at 0x7f9635bb3870>) ('Value at 0 is :', <generator object Question5 at 0x7f9635bb3870>) ('Value at 12345643 is :', <generator object Question5 at 0x7f9635bb3870>)

Does anyone know what I'm doing wrong in this situation? Thank you.

最满意答案

在这种情况下，您不需要收益率。

您需要的算法取决于您是否知道喜欢列表的大小。

尺寸已知

给定列表n大小：只返回列表的nm -th元素。

尺寸未知

两次迭代

最简单的技巧是首先迭代整个列表，计算它包含的元素数量。然后你知道大小n并获得如上所述的元素。

记住m个元素

如果你“记住”你在列表中看到的最后m个元素，你也可以在一次迭代中解决这个问题。然后迭代直到列表的结尾并返回您仍记得的“最旧”元素。

使用两个指针

最后一种方法使用指向列表中两个元素的两个指针，这两个元素总是具有m个元素的距离。它们都是同时移动的。如果第一个指针到达列表的末尾，则第二个指针正好指向列表末尾的元素m个元素。

请参阅如何从单链表的末尾查找第n个元素？详情。该帖子中的代码是C ++，但它不应该太难理解。

You don't need yield in that case.

The algorithm you need depends on whether you know the size of the liked list or not.

Size known

Given size of list n: Just return the n-m-th element of the list.

Size unknown

Two iterations

The simplest trick would be to iterate over the whole list first, counting how many elements it contains. Then you know the size n and get the element as described above.

Remembering m elements

You can also solve this in one iteration if you 'remember' the last m elements you've seen in the list. Then iterate until the end of the list and return the 'oldest' element you still remember.

Using two pointers

This last approach uses two pointers to two elements of the list that always have a distance of m elements. They are both moved simultaneously. If the first pointer reaches the end of the list, the second pointer exactly points to the element m elements from the end of the list.

See How to find nth element from the end of a singly linked list? for details. The code in that post is C++, but it shouldn't be too hard to understand.

更多推荐