求解释一行python code

leetcode 第200题

solution code来自 https://www.jiuzhang.com/solutio ... ghlight-lang-python python 的第60行
     在网站是公开的，付不付费都能看，不存在侵犯版权的问题

1. from collections import deque
   
2. 
   
3. class Solution:
   
4.     def numIslands(self, grid: List[List[str]]) -> int:
   
5.         
   
6.         if not grid or not grid[0]:
   
7.             return 0
   
8.         
   
9.         island = 0
   
10.         for i in range(len(grid)):
    
11.             for j in range(len(grid[0])):
    
12.                 if grid[i][j] == "1":
    
13.                     self.bfs(grid,i,j)
    
14.                     island += 1
    
15.         return island
    
16.             
    
17.     def bfs(self, grid, x, y):
    
18.         
    
19.         queue = deque([(x,y)]) #这里如果写成 deque([x,y]), 就会出现  int is not iterable,导致两种不同的结果的原因是什么呢？
    
20.         grid[x][y] = "0"
    
21.         
    
22.         while queue:
    
23.             x, y = queue.popleft()
    
24. 
    
25.             for delta_x, delta_y in ([1,0],[-1,0],[0,1],[0,-1]):
    
26.                 next_x = x + delta_x
    
27.                 next_y = y + delta_y
    
28.                 if not self.is_valid(grid,next_x,next_y):
    
29.                     continue
    
30.                     
    
31.                 grid[next_x][next_y] = "0"
    
32.                 queue.append((next_x,next_y))
    
33.                
    
34.                
    
35.     def is_valid(self,grid,x,y):
    
36.         m = len(grid)
    
37.         n = len(grid[0])
    
38.         return 0 <= x < m and 0 <= y <n and grid[x][y] == "1"

复制代码

我的问题是 queue = deque([(x,y)]) #这里如果写成 deque([x,y]), 就会出现  int is not iterable,导致两种不同的结果的原因是什么呢？

ShikiH 发表于 2019/05/28 08:58:41
算是对楼上的一点补充：
这里用deque而不是用list是因为list pop(0)是o(n)，但是deque popleft()只要o(1)
详见：https://wiki.python.org...

对，所以不用pop，而是用for loop iterate下一个元素（队首元素），时间是O(1)，直接用list就可以了

抱歉，上面第六行写错了，不能直接更新x, y

1. def bfs(self, grid, x, y):
   
2.     q = [(x, y)]
   
3.     grid[x][y] = "0"
   
4.     for x, y in q:
   
5.         for dx, dy in ((1,0),(-1,0),(0,1),(0,-1)):
   
6.                 nx, ny = x+dx, y+dy
   
7.                 if self.is_valid(grid, nx, ny):
   
8.                         grid[nx][ny] = "0"
   
9.                         q.append((nx, ny))
   
10.     return 1

复制代码

顺便如果你让你的bfs返回一个1的话，上面island的计算也可以用list comprehension来算出来了

1. def numIslands(self, grid):
   
2.     m, n = len(grid), len(grid) and len(grid[0])
   
3.     return sum(self.bfs(grid, i, j) for i in range(m) for j in range(n) if grid[i][j] == "1")

复制代码

Python里的FIFO queue操作可以直接用一个for list，因为Python list是动态的，本身是可以不断被更新
就比如这个例子，就可以写成：

1. def bfs(self, grid, x, y):
   
2.     q = [(x, y)]
   
3.     grid[x][y] = "0"
   
4.     for x, y in q:
   
5.         for dx, dy in ((1,0),(-1,0),(0,1),(0,-1)):
   
6.                 x, y = x+dx, y+dy
   
7.                 if self.is_valid(grid, x, y):
   
8.                         grid[x][y] = "0"
   
9.                         q.append((x, y))

复制代码

当然，queue里面元素应该是一个(x, y)，而不是x或者y，所以初始化是要[(x, y)]

令狐冲老师的Python第60行吗？是空行啊。。

看了下 九章的题解渲染有问题 标的行数和实际行数不对应 楼主发一下究竟要问哪一行

一剑终情 发表于 2019-5-27 23:16
看了下 九章的题解渲染有问题 标的行数和实际行数不对应 楼主发一下究竟要问哪一行

谢谢！ 在我发的code的第19行，代码上也有注明问题

补充内容 (2019-5-28 00:33):
在原网站是被comment 了， 因为原网站给的是lintcode的题解，leetcode版本在comment里

大概就是这样的
那个报错不是出在deque([x, y])的时候，是出在x, y = queue.popleft()的时候
因为你这里写了x, y = queue.popleft()，所以会要求这个deque里面的元素一定要是能分解成x, y的。你要是用deque([x, y])的化，那么这个deque是有两个int元素，你popleft出来只是一个int，没办法分解成两个int

yao zou 发表于 2019-5-28 01:05
大概就是这样的
那个报错不是出在deque([x, y])的时候，是出在x, y = queue.popleft()的时候
因为你这 ...

有道理，所以while queue并没有循环queue对吗？只要queue不为空就可以？

林红玉 发表于 2019-5-28 02:06
有道理，所以while queue并没有循环queue对吗？只要queue不为空就可以？

Python里面while (xxxx)这个语句的意思就是，如果xxxx是boolean的化，判断xxxx是不是True。否则将xxxx转换到boolean判断是不是True
如果xxxx是一个空容器的化，它转换到boolean就是False

yao zou 发表于 2019-5-28 02:14
Python里面while (xxxx)这个语句的意思就是，如果xxxx是boolean的化，判断xxxx是不是True。否则将xxxx转 ...

懂了～开心得原地转圈圈感谢～～～