1.最短的桥:
这个题我最新的代码如下:
from collections import deque
class Solution:
def shortestBridge(self,grid:List[List[int]])->int:
nr=len(grid)
if nr==0:
return 0
nc=len(grid[0])
island=deque([])
for r in range(nr):
for c in range(nc):
if grid[r][c]==1:
q=deque([(r,c)])
island=deque([(r,c)])
while q:
(r,c)=q.popleft()
grid[r][c]=-1
for x,y in ([r+1,c],[r-1,c],[r,c+1],[r,c-1]):
if 0<=x<=nr-1 and 0<=y<=nc-1 and grid[x][y]==1:
q.append((x,y))
grid[x][y]=-1
island.append([x,y])
break
if island:
break
step=0
while 1:
q=island
island=deque([])
while q:
(r,c)=q.popleft()
for x,y in ([r+1,c],[r-1,c],[r,c+1],[r,c-1]):
if 0<=x<=nr-1 and 0<=y<=nc-1 and grid[x][y]==0:
grid[x][y]==-1
island.append([x,y])
elif 0<=x<=nr-1 and 0<=y<=nc-1 and grid[x][y]==1:
return step
step+=1
1.代码能过但是超内存了,原因是我创建了大量的deque,导致旧的deque没有删掉,所以超内存了。你现在想这么个逻辑,那就是,为什么前面要用deque,是因为你现在不知道自己要遍历多久才能停,所以才用deque去搜索,现在你都有了island的列表,你根本不需要使用的确来去做这个事情,也就是说你可以直接去遍历island里的所有的元素,这样的话就不需要重复的建立新的deque。就能把内存省下来了
2.另外,在遇见0的时候别忘了置-1,我第一次做的时候忘记这个了