我用一排蹦床進行編碼練習，每個蹦床都有最小和最大“彈力”。我有起始蹦床和結束蹦床的索引，有了這個，我需要找到從起始蹦床到達結束蹦床所需的最小跳躍量。我嘗試創建一個鄰接列表，其中列出了所有可能的蹦床跳躍。這很好，直到我到達大量蹦床為止。問題是它需要 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 個嵌套循環。有誰知道更有效的方法嗎？（最好沒有循環）
1 回答
蠱毒傳說
TA貢獻1895條經驗 獲得超3個贊
假設“彈性”嚴格為正，您可以省略這部分：
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 搜索過程中很可能沒有訪問到所有蹦床。在這種情況下，創建完整的鄰接表就是浪費時間......
添加回答
舉報
0/150
提交
取消