用于练习邻接表和 BFS 的编码练习

Question

我用一排蹦床进行编码练习，每个蹦床都有最小和最大“弹力”。我有起始蹦床和结束蹦床的索引，有了这个，我需要找到从起始蹦床到达结束蹦床所需的最小跳跃量。我尝试创建一个邻接列表，其中列出了所有可能的蹦床跳跃。这很好，直到我到达大量蹦床为止。问题是它需要 O(n^2) 时间。这就是我创建邻接列表的方式：def createAL (a, b, l):al = [list() for _ in range(l)]for i in range(l):        for j in range(a[i], b[i]+1):        if (i+j) <= l-1:            al[i].append(i+j)        if (i-j) >= 0:            al[i].append(i-j)for i in range(len(al)):    al[i] = list(set(al[i]))return al“a”是最小值。弹性，“b”最大弹性，“l”是两个列表的长度。如您所见，问题是我有 2 个嵌套循环。有谁知道更有效的方法吗？（最好没有循环）

Answer 1

假设“弹性”严格为正，您可以省略这部分：

for i in range(len(al)):
    al[i] = list(set(al[i]))

...因为这些列表中不可能有重复项。

（但是，如果弹性可能为 0 或负数，则首先将 中低于 1 的任何值替换为 1 a）

的构建a可以通过以下方式加快一点：

• 在实际目标索引上设置范围（因此您不需要i+j在每个循环中都需要），

• 使用min()and剪切这些范围max()，避免if循环中的语句

• 使用列表理解避免单独append调用

结果：

al = [
    [*range(max(0, i-b[i]), i-a[i]+1), *range(i+a[i], min(l, i+b[i]+1))]
            for i in range(l)
]

最后，由于该邻接列表可能服务于 BFS 算法，因此您还可以认为构建邻接列表可能不是必需的，因为在BFS 期间查找相邻节点是小菜一碟a，b现场使用。我想知道您是否真的通过创建邻接表来节省时间。

在你的 BFS 代码中，你可能有这样的东西（i“当前”节点在哪里）：

for neighbor in al[i]:

这可以替换为：

for neighbor in (*range(max(0, i-b[i]), i-a[i]+1), *range(i+a[i], min(l, i+b[i]+1))):

我们还应该意识到，如果在远小于蹦床数量的步骤中找到目标蹦床，那么在 BFS 搜索过程中很可能没有访问到所有蹦床。在这种情况下，创建完整的邻接表就是浪费时间......