python用list比queue快？
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了python用list比queue快？，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1705字，纯文字阅读大概需要3分钟。
内容图文
今天在做题的时候，遇到一个BFS，第一反应还是队列，结果玄而又玄的过了，看了下其他人的代码，发现快的全是用list做的。
差很多的那种，看情况也不是因为leetcode判题时间随机的样子。
传送门 地图分析
你现在手里有一份大小为 N x N 的『地图』（网格） grid，上面的每个『区域』（单元格）都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，你知道距离陆地区域最远的海洋区域是是哪一个吗？请返回该海洋区域到离它最近的陆地区域的距离。
我们这里说的距离是『曼哈顿距离』（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个区域之间的距离是 |x0 - x1| + |y0 - y1| 。
如果我们的地图上只有陆地或者海洋，请返回 -1。
示例：
输入：[[1,0,1],[0,0,0],[1,0,1]] 输出：2 解释： 海洋区域 (1, 1) 和所有陆地区域之间的距离都达到最大，最大距离为 2。
提示：
-
1 <= grid.length == grid[0].length <= 100 -
grid[i][j]不是0就是1
很简单的BFS，从陆地开始搜索就行了。
使用队列 ： 1548 ms 两倍，弹出队列造成的？
import
queue
class
Solution:
def maxDistance(self, grid) -> int:
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
n = len(grid)
q = queue.Queue()
vis = dict()
max_dis = -1
for i in range(n):
for j in range(n):
if grid[i][j] == 1:
q.put([i, j, 0])
vis[(i, j)] = 0
whilenot q.empty():
x, y, cnt = q.get()
for i in range(4):
tx = x + dx[i]
ty = y + dy[i]
if 0 <= tx < n and 0 <= ty < n and (tx, ty) notin vis:
max_dis = max(max_dis, cnt + 1)
vis[(tx, ty)] = cnt + 1
q.put([tx, ty, cnt + 1])
return max_dis
使用list： 时间是 712 ms
import
queue
class
Solution:
def maxDistance(self, grid: List[List[int]]) -> int:
dx = [0,1,0,-1]
dy = [1,0,-1,0]
n = len(grid)
q = list()
vis = dict()
max_dis = -1
for i in range(n):
for j in range(n):
if grid[i][j] == 1:
q.append([i,j,0])
vis[(i,j)] = 0
if len(q) == 0:
return -1
while len(vis) < n*n:
tmp = []
for x,y,cnt in q:
for i in range(4):
tx = x + dx[i]
ty = y + dy[i]
if 0 <= tx < n and 0 <= ty < n and (tx,ty) notin vis:
max_dis = max(max_dis, cnt+1)
vis[(tx,ty)] = cnt + 1
tmp.append([tx, ty, cnt+1])
q = tmp.copy()
return max_dis
原文：https://www.cnblogs.com/xxfna/p/11612228.html
内容总结
以上是互联网集市为您收集整理的python用list比queue快？全部内容，希望文章能够帮你解决python用list比queue快？所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。