用于练习邻接表和 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&nbsp;i&nbsp;in&nbsp;range(len(al)): &nbsp;&nbsp;&nbsp;&nbsp;al[i]&nbsp;=&nbsp;list(set(al[i]))...因为这些列表中不可能有重复项。（但是，如果弹性可能为 0 或负数，则首先将 中低于 1 的任何值替换为 1&nbsp;a）的构建a可以通过以下方式加快一点：在实际目标索引上设置范围（因此您不需要i+j在每个循环中都需要），使用min()and剪切这些范围max()，避免if循环中的语句使用列表理解避免单独append调用结果：al&nbsp;=&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;[*range(max(0,&nbsp;i-b[i]),&nbsp;i-a[i]+1),&nbsp;*range(i+a[i],&nbsp;min(l,&nbsp;i+b[i]+1))] &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;i&nbsp;in&nbsp;range(l) ]最后，由于该邻接列表可能服务于 BFS 算法，因此您还可以认为构建邻接列表可能不是必需的，因为在BFS 期间查找相邻节点是小菜一碟a，b现场使用。我想知道您是否真的通过创建邻接表来节省时间。在你的 BFS 代码中，你可能有这样的东西（i“当前”节点在哪里）：for&nbsp;neighbor&nbsp;in&nbsp;al[i]:这可以替换为：for&nbsp;neighbor&nbsp;in&nbsp;(*range(max(0,&nbsp;i-b[i]),&nbsp;i-a[i]+1),&nbsp;*range(i+a[i],&nbsp;min(l,&nbsp;i+b[i]+1))):我们还应该意识到，如果在远小于蹦床数量的步骤中找到目标蹦床，那么在 BFS 搜索过程中很可能没有访问到所有蹦床。在这种情况下，创建完整的邻接表就是浪费时间......