徐州网约车,网站内容优化方法有哪些内容,培训网站建设机构,电子商务网站建设与维护方法200. 岛屿数量
200. 岛屿数量时间#xff1a;O(mn)#xff1b;空间#xff1a;O(min(m, n))#xff0c;队列最大入队个数#xff0c;可以想象从左上到右下#xff0c;第一次入队1个#xff0c;第二次出队1#xff0c;入队2#xff0c;第三次出队2#xff0c;入队3……200. 岛屿数量
200. 岛屿数量时间O(mn)空间O(min(m, n))队列最大入队个数可以想象从左上到右下第一次入队1个第二次出队1入队2第三次出队2入队3…
class Solution {
public:int dir[4][2] {0, 1, 1, 0, 0, -1, -1, 0}; // 右下左上int count 0;int row;int column;void bfs(vectorvectorchar grid, int x, int y){queuepairint, intq;q.push({x, y});while(!q.empty()){auto t q.front();q.pop();for(int i 0; i 4; i){int new_x t.first dir[i][0], new_y t.second dir[i][1];if(new_x 0 || new_x row || new_y 0 || new_y column){continue;}if(grid[new_x][new_y] ! 1){continue;}grid[new_x][new_y] 0; // 访问q.push({new_x, new_y});}}}int numIslands(vectorvectorchar grid) {// bfsrow grid.size(), column grid[0].size();for(int i 0; i row; i){for(int j 0; j column; j){if(grid[i][j] 1){bfs(grid, i, j);count;}}}return count;}
};695. 岛屿的最大面积
695. 岛屿的最大面积同上bfs
class Solution {
public:int dir[4][2] {0, 1, 1, 0, 0, -1, -1, 0}; // 右下左上int ret 0;int row;int column;int bfs(vectorvectorint grid, int x, int y){grid[x][y] 0;queuepairint, intq;q.push({x, y});int square 1;while(!q.empty()){auto t q.front();q.pop();for(int i 0; i 4; i){int new_x t.first dir[i][0], new_y t.second dir[i][1];if(new_x 0 || new_x row || new_y 0 || new_y column){continue;}if(grid[new_x][new_y] ! 1){continue;}grid[new_x][new_y] 0; // 访问square;q.push({new_x, new_y});}}return square;}int maxAreaOfIsland(vectorvectorint grid) {// bfsrow grid.size(), column grid[0].size();for(int i 0; i row; i){for(int j 0; j column; j){if(grid[i][j] 1){int temp bfs(grid, i, j);ret max(ret, temp);}}}return ret;}
};547. 省份数量
547. 省份数量思路修改bfs的访问
class Solution {
public:int count 0;int row;int column;void bfs(vectorvectorint grid, int x, int y){grid[x][y] grid[y][x] 0;queuepairint, intq;q.push({x, y});while(!q.empty()){auto t q.front();q.pop();int new_x t.first;for(int i 0; i column; i){if(grid[new_x][i] 0){continue;}grid[new_x][i] grid[i][new_x] 0; // 访问q.push({i, new_x});}}}int findCircleNum(vectorvectorint isConnected) {// bfsrow isConnected.size(), column isConnected[0].size();for(int i 0; i row; i){for(int j 0; j column; j){if(isConnected[i][j] 1){bfs(isConnected, i, j);count;}}}return count;}
};
