引言:
为了一个广度优先搜索的细节有必要水一整篇文章?有必要。
这个细节非常重要,以至于我在切Leetcode某一题的时候,明明和答案的高效率通过的代码相差无几,逻辑毫无错误,STL使用相同,但仍然有几个测试点卡不过去。
题目来源:200.岛屿数量
我原来的代码:
1 class Solution { 2 public: 3 int numIslands(vector<vector<char>>& grid) { 4 // vector<vector<bool>> visited(grid.size(),vector<bool>(grid[0].size(),false)); 5 //int dx[4] = {1,0,-1,0}; 6 //int dy[4] ={0,-1,0,1}; 7 int res = 0; 8 int r= grid.size(); 9 int c = grid[0].size(); 10 for(int i = 0;i<r;++i){ 11 for(int j =0;j<c;++j){ 12 if(grid[i][j] == '0')continue; 13 queue<pair<int,int>> q; 14 q.push({i,j}); 15 res ++; 16 grid[i][j] = '1'; 17 while(!q.empty()){ 18 int x = q.front().first; 19 int y = q.front().second; 20 q.pop(); 21 grid[x][y] = '0'; 22 /* 23 for(int k = 0;k<4;++k){ 24 int xx = x+dx[k]; 25 int yy = y+dy[k]; 26 if(xx<0||xx>=grid.size() ||yy<0||yy>=grid[0].size()||grid[xx][yy]=='0'){ 27 continue; 28 } 29 q.push(make_pair(xx,yy)); 30 }*/ 31 if(x-1>=0 && grid[x-1][y]=='1')q.push({x-1,y}); 32 if(y-1>=0 &&grid[x][y-1]=='1')q.push({x,y-1}); 33 if(x+1<r&&grid[x+1][y]=='1')q.push({x+1,y}); 34 if(y+1<c&&grid[x][y+1]=='1')q.push({x,y+1}); 35 } 36 } 37 } 38 return res; 39 } 40 };
代码运行后,总是超时。
我做了许多猜测与尝试,排除了 另外开visited数组、make_pair、dx[]与dy[]、甚至访问vector的size()等可能导致超时的因素。
但是都没有太大的效果。
于是排除所有可能,真相就只有一个了——
先来看看答案代码:
1 class Solution { 2 public: 3 int numIslands(vector<vector<char>>& grid) { 4 int nr = grid.size(); 5 if (!nr) return 0; 6 int nc = grid[0].size(); 7 8 int num_islands = 0; 9 for (int r = 0; r < nr; ++r) { 10 for (int c = 0; c < nc; ++c) { 11 if (grid[r][c] == '1') { 12 ++num_islands; 13 grid[r][c] = '0'; 14 queue<pair<int, int>> neighbors; 15 neighbors.push({r, c}); 16 while (!neighbors.empty()) { 17 auto rc = neighbors.front(); 18 neighbors.pop(); 19 int row = rc.first, col = rc.second; 20 if (row - 1 >= 0 && grid[row-1][col] == '1') { 21 neighbors.push({row-1, col}); 22 grid[row-1][col] = '0'; 23 } 24 if (row + 1 < nr && grid[row+1][col] == '1') { 25 neighbors.push({row+1, col}); 26 grid[row+1][col] = '0'; 27 } 28 if (col - 1 >= 0 && grid[row][col-1] == '1') { 29 neighbors.push({row, col-1}); 30 grid[row][col-1] = '0'; 31 } 32 if (col + 1 < nc && grid[row][col+1] == '1') { 33 neighbors.push({row, col+1}); 34 grid[row][col+1] = '0'; 35 } 36 } 37 } 38 } 39 } 40 41 return num_islands; 42 } 43 }; 44 作者:LeetCode 45 链接:https://leetcode-cn.com/problems/number-of-islands/solution/dao-yu-shu-liang-by-leetcode/ 46 来源:力扣(LeetCode) 47 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
对比可以发现,答案与我的代码里面一个看似没什么影响的差别在于:
我的代码是从队列中弹出节点时才把这个节点标记为<已访问>,而答案代码里是在push进队列的时候就标记其为<未访问>。
看似没有什么逻辑问题啊。
但是,
我仔细
仔细
想了想。
这实际上导致的效率差别是巨大的!
比如,在访问cur节点的时候,把一个B节点push了进队列(也就是说B节点是cur节点的邻居节点),
如果我此刻没有标记其为<已访问>的话,
那么我在访问队列中排在B前面的节点cur2时(即在cur之后,B之前,被push进队列的节点),
如果我在cur2的邻居节点里看到了B,此刻由于B还没有出队列,所以它目前未被标记为<已访问>
那么,此时B又会再一次被push进队列里面!!!
也就是说,一个节点会被访问多次,那运行时间固然就翻倍了。
由此可见这个细节的重要性之大。
如果比赛的时候因为这个细节卡题了的话,我想我就不会痛失倒一了吧。