练习邻接表和 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

假设“bounciness”严格为正，你可以省略这部分：

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

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

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

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

在实际目标索引上设置范围（因此您不需要在每个循环中都使用 i+j），
使用 min() 和 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 on-the-spot 小菜一碟。我不知道你是否真的通过创建邻接表来赢得时间。

在你的 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))):

我们还应该意识到，如果在远小于trampolines个数的步数中找到了目标trampoline，那么BFS搜索时有可能没有访问到所有trampolines。在那种情况下，创建完整的邻接表将是浪费时间...

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

Coding exercise for practicing adjacency list and BFS

python

algorithm

breadth-first-search

adjacency-list