Я хотел бы знать, что я могу делать неправильно, пытаясь найти число узлов, соединенных в цикле.Вот моя реализация на python.
# Defined Node class
class Node(object):
data = 0
def __init__(self, data=None, next_node=None):
self.data = self.increment()
self.next = next_node
def increment(self):
Node.data += 1
return Node.data
def setNext(self, next_node = None):
self.next = next_node
Я определил функцию для создания цепочки узлов, взяв произвольное количество узлов и желаемую длину цикла в качестве параметров.
def create_chain(num_of_nodes, loop_size):
nodes = [Node() for _ in range(num_of_nodes)]
if loop_size == 0:
return nodes[0]
else:
for node, next_node in zip(nodes, nodes[1:]):
node.next = next_node
# cleaned_nodes.append(node)
nodes[num_of_nodes-1].next = nodes[(num_of_nodes - loop_size)-1]
return nodes[0]
Затем я определил функцию для определения размера цикла с учетом начального узла, который был передан в качестве параметра функции.
def loop_size(node):
count = 0
if node == None:
return 1
if node.next == None:
return 1
slow = fast = node
while(slow or fast or node.next):
count += 1
if fast.next == None:
#count += 1
break
if slow == fast.next or slow == fast.next.next:
count += 1
break
slow = slow.next
fast = fast.next.next
return count
Я написал несколько тестов, но это конкретное утверждение не сработало, и яМне бы хотелось понять, почему.
def test_very_long_chain(self):
self.chain = create_chain(3904, 1087)
self.assertEqual(loop_size(self.chain), 10, 'Loop size of 10 expected')
Я получаю эту ошибку утверждения;
AssertionError: 3264 != 10 : Loop size of 10 expected
Я бы очень признателен за некоторые рекомендации по этому вопросу.Спасибо