我用一排蹦床進行編碼練習(xí)，每個蹦床都有最小和最大“彈力”。我有起始蹦床和結(jié)束蹦床的索引，有了這個，我需要找到從起始蹦床到達結(jié)束蹦床所需的最小跳躍量。我嘗試創(chuàng)建一個鄰接列表，其中列出了所有可能的蹦床跳躍。這很好，直到我到達大量蹦床為止。問題是它需要 O(n^2) 時間。這就是我創(chuàng)建鄰接列表的方式：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(fā)”是兩個列表的長度。如您所見，問題是我有 2 個嵌套循環(huán)。有誰知道更有效的方法嗎？（最好沒有循環(huán)）
1 回答
蠱毒傳說
TA貢獻1895條經(jīng)驗 獲得超3個贊
假設(shè)“彈性”嚴格為正，您可以省略這部分：
for i in range(len(al)): al[i] = list(set(al[i]))
...因為這些列表中不可能有重復(fù)項。
（但是，如果彈性可能為 0 或負數(shù)，則首先將 中低于 1 的任何值替換為 1 a）
的構(gòu)建a可以通過以下方式加快一點：
在實際目標(biāo)索引上設(shè)置范圍（因此您不需要
i+j在每個循環(huán)中都需要），使用
min()and剪切這些范圍max()，避免if循環(huán)中的語句使用列表理解避免單獨
append調(diào)用
結(jié)果：
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) ]
最后，由于該鄰接列表可能服務(wù)于 BFS 算法，因此您還可以認為構(gòu)建鄰接列表可能不是必需的，因為在BFS 期間查找相鄰節(jié)點是小菜一碟a，b現(xiàn)場使用。我想知道您是否真的通過創(chuàng)建鄰接表來節(jié)省時間。
在你的 BFS 代碼中，你可能有這樣的東西（i“當(dāng)前”節(jié)點在哪里）：
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))):
我們還應(yīng)該意識到，如果在遠小于蹦床數(shù)量的步驟中找到目標(biāo)蹦床，那么在 BFS 搜索過程中很可能沒有訪問到所有蹦床。在這種情況下，創(chuàng)建完整的鄰接表就是浪費時間......
添加回答
舉報
0/150
提交
取消