检查循环长度的函数

Question

嘿伙计们，我有这个功能，但是当我测试它时它给了我错误。有没有人知道如何解决它这是我的练习。请仔细阅读。

编写一个函数 cycleLength(array)，其中 returns 形成一个循环的学生人数，前提是您首先与最左边的学生交谈。输入数组是一个非负整数列表，这样 array[m] 就是学生 m 重定向到的学生的编号。没有学生重定向到他自己。最左边的学生是 0 号，下一个是 1 号，依此类推。列表中的每个元素都在 [0, n-1] 范围内，其中 n 是列表的长度。例如，假设列表是 [1, 3, 0, 1]。然后学生 0 重定向到学生 1，学生 1 重定向到学生 3，学生 3 重定向回学生 1。有两个学生的循环：1、3。因此答案将是 2。请注意，即使您从学生 0 开始，他不是循环的一部分。这是我的功能：

def cycleLength(m):
    lst = []
    i = 0
    while i not in lst:
        lst.append(i)
        i = int(m[i])

    b = len(lst) - lst.index(i)
    return b

Answer 1

def cycleLength(m):
    lst = []
    for x in m:  
        if x in lst:
            return len(lst) - lst.index(x)
        lst.append(x)     

    return -1

解释：

你应该在索引 i m[i] 处的元素不在 lst 中时循环 - 你所做的是在列表中查找索引而不是 "the element at index"
与上一点相同，您应该附加到 lst 元素 - 而不是元素的索引 - 否则您将找不到任何此类 "duplicate" 元素 - 因为索引应该只是增加。
关于最后一点 - 索引应在每次迭代中不断增加
最后，循环的长度是从元素第一次出现到下一次迭代相同元素的时间。而且不一定从列表的开头开始。

更正：

以前版本的代码有错误，这里发布了相同想法的更简单版本，并且也没有错误（我相信）。 -1代表"no cycles found".

Answer 2

你几乎答对了。

>>> def cycleLength(students):
...     seen = []
...     current = 0
...     # Run till we have seen all the students
...     while len(seen) != len(students):
...         # If the current index has been seen already
...         if current in seen:
...             return len(seen) - seen.index(current)
...         seen.append(current)
...         current = students[current]
... 
>>> assert(cycleLength([1, 3, 0, 1]) == 2)
>>> assert(cycleLength([1, 3, 0, 2]) is None)

这也会处理没有循环的情况。

检查循环长度的函数

function that checks the length of the cycle

python

list

function

python-2.7

cycle