制作网页和网站的区别,化学试剂网站建设,江桥网站建设,济南长清网站建设目录
1 200. 岛屿数量
2 994. 腐烂的橘子
2.1 智障遍历法
2.2 仿层序遍历法 菜鸟做题#xff0c;语言是 C 1 200. 岛屿数量
解题思路#xff1a;
遍历二维数组#xff0c;寻找 “1”#xff08;若找到则岛屿数量 1#xff09;寻找与当前 “1” 直接或间接连接在…目录
1 200. 岛屿数量
2 994. 腐烂的橘子
2.1 智障遍历法
2.2 仿层序遍历法 菜鸟做题语言是 C 1 200. 岛屿数量
解题思路
遍历二维数组寻找 “1”若找到则岛屿数量 1寻找与当前 “1” 直接或间接连接在一起的 “1”将这些 “1” 置为 “0”再寻找下一个 “1”
思路说明图 如步骤 1 所示我们找到 “1”红框内部它可以作为一个岛屿的开头。接下来我们寻找与这个 “1” 直接或间接连接在一起的 “1”如步骤 2 所示。这一坨 “1”红框内部构成一个岛屿。 直接连接 是指上下左右四个方向斜对角方向的不算。 除此之外为了避免我们下一次寻找 “1” 时把这座岛屿内部的 “1” 视为下一个岛屿的开头我们要将这些 “1” 置为 “0” 。 我们是对整个二维数组进行遍历的若不在遍历完一座岛屿后将 “1” 置为 “0”那么这座岛屿除开头之外的 “1” 会被误认为是下一座岛屿的开头。 具体代码
① Find “1”在二维数组中寻找 “1”作为岛屿的开头。
for (int i 0; i nr; i) {for (int j 0; j nc; j) {if (grid[i][j] 1) {count;helper(grid, i, j);}}
} nr 是二维数组的行数nc 是二维数组的列数。一旦找到 “1” 就 count即认为找到了一座新的岛屿。同时使用 helper 函数去寻找与当前 “1” 直接或间接连接在一起的 “1” 。 ② Find Island寻找与当前 “1” 直接或间接连接在一起的 “1”它们构成一座岛屿。
void helper(vectorvectorchar grid, int r, int c) {int nr grid.size();int nc grid[0].size();grid[r][c] 0;if (r - 1 0 grid[r - 1][c] 1) helper(grid, r - 1, c);if (r 1 nr grid[r 1][c] 1) helper(grid, r 1, c);if (c - 1 0 grid[r][c - 1] 1) helper(grid, r, c - 1);if (c 1 nc grid[r][c 1] 1) helper(grid, r, c 1);
} 这四个 if 其实就是做上下左右四个方向的边界判断同时判断当前 “1” 的邻居是不是 “1” 。若找到相邻的 “1”那么再递归寻找与相邻的 “1” 直接或间接连接在一起的 “1” 。 class Solution {
public:void helper(vectorvectorchar grid, int r, int c) {int nr grid.size();int nc grid[0].size();grid[r][c] 0;if (r - 1 0 grid[r - 1][c] 1) helper(grid, r - 1, c);if (r 1 nr grid[r 1][c] 1) helper(grid, r 1, c);if (c - 1 0 grid[r][c - 1] 1) helper(grid, r, c - 1);if (c 1 nc grid[r][c 1] 1) helper(grid, r, c 1);}int numIslands(vectorvectorchar grid) {int nr grid.size();if (nr 0) return 0;int nc grid[0].size();int count 0;for (int i 0; i nr; i) {for (int j 0; j nc; j) {if (grid[i][j] 1) {count;helper(grid, i, j);}}}return count;}
}; 2 994. 腐烂的橘子
与 200. 岛屿数量 像又不像区别在于是否有时间观念
2.1 智障遍历法
解题思路
每个时刻都遍历二维数组寻找腐烂的橘子2对位于腐烂的橘子2四周的新鲜橘子1进行污染直到所有新鲜橘子都被污染或者无法继续污染
具体代码
① 寻找腐烂的橘子2与 200 题的代码几乎一样。
for (int i 0; i nr; i) {for (int j 0; j nc; j) {if (temp[i][j] 2)helper(grid, i, j);}
}
② 对位于腐烂的橘子2四周的新鲜橘子1进行污染。
void helper(vectorvectorint grid, int r, int c) {if (r - 1 0 grid[r - 1][c] 1) grid[r - 1][c] 2;if (r 1 nr grid[r 1][c] 1) grid[r 1][c] 2;if (c - 1 0 grid[r][c - 1] 1) grid[r][c - 1] 2;if (c 1 nc grid[r][c 1] 1) grid[r][c 1] 2;
}
③ 判断是否所有的新鲜橘子1都被污染。
bool isRotted(vectorvectorint grid) {for (int i 0; i nr; i) {for (int j 0; j nc; j) {if (grid[i][j] 1) return false;}}return true;
}
④ 判断是否无法继续污染在进行新一轮污染之前先把上一轮的污染结果 grid 存入 temp 中如果这一轮污染后有 temp grid则说明已经无法继续污染了。
vectorvectorint temp grid;
for (int i 0; i nr; i) {for (int j 0; j nc; j) {if (temp[i][j] 2)helper(grid, i, j);}
}
if (temp grid) return -1; 这样做还有一个好处就是可以通过 if (temp[i][j] 2) 来寻找腐烂的橘子避免在这一轮中新腐烂的橘子参与到污染中。 class Solution {
public:int nr, nc;void helper(vectorvectorint grid, int r, int c) {if (r - 1 0 grid[r - 1][c] 1) grid[r - 1][c] 2;if (r 1 nr grid[r 1][c] 1) grid[r 1][c] 2;if (c - 1 0 grid[r][c - 1] 1) grid[r][c - 1] 2;if (c 1 nc grid[r][c 1] 1) grid[r][c 1] 2;}bool isRotted(vectorvectorint grid) {for (int i 0; i nr; i) {for (int j 0; j nc; j) {if (grid[i][j] 1) return false;}}return true;}int orangesRotting(vectorvectorint grid) {nr grid.size();nc grid[0].size();int count 0;while (!isRotted(grid)) {vectorvectorint temp grid;for (int i 0; i nr; i) {for (int j 0; j nc; j) {if (temp[i][j] 2)helper(grid, i, j);}}if (temp grid) return -1;count;if (isRotted(grid)) return count;}return count;}
}; 2.2 仿层序遍历法
参考官方题解进行了升级仿二叉树的层序遍历不用像 2.1 那样每次都进行全部遍历
核心思想将属于同一时刻的腐烂橘子视为属于同一层。 上图画出了橘子逐步腐烂的 5 个时刻每个时刻中打红叉的腐烂橘子属于同一层打灰叉的腐烂橘子属于上一层。 解题思路
将属于同一时刻的腐烂橘子送入队列中出队并遍历属于同一时刻的腐烂橘子对四周的新鲜橘子进行污染并送入队列中
思路说明图 对于时刻 1让腐烂的橘子入队对于时刻 2队列中的腐烂橘子出队让它们对四周的新鲜橘子进行污染最后将新被污染的橘子入队。以此类推。 在一轮污染中如果有橘子被污染则计时器 1同时判断新鲜橘子是否被污染完毕如果没有橘子被污染则跳出循环同时判断新鲜橘子是否被污染完毕。若没有橘子被污染且新鲜橘子没有被污染完毕则表明无法污染所有新鲜橘子。 具体代码
① 初始化
计数新鲜橘子的数量即 freshCount 1记录腐烂橘子的位置即将横纵坐标送入队列中
int freshCount 0;
queuepairint, int q;
for (int i 0; i nr; i) {for (int j 0; j nc; j) {if (grid[i][j] 1) {freshCount;} else if (grid[i][j] 2) {q.push(make_pair(i, j));}}
} nr 是 grid 的行数nc 是 grid 的列数。 ② 循环结构和二叉树的层序遍历一模一样
获取当前层中腐烂橘子的个数遍历当前层中的腐烂橘子
while (!q.empty()) {int currentSize q.size();for (int i 0; i currentSize; i) {pairint, int pos q.front();q.pop();// 对橘子进行污染}
}
③ 针对每个腐烂橘子对其四周进行污染
判断上/下/左/右位置是否越界若越界则跳过该位置若该位置上的是新鲜橘子则进行污染并将其入队同时将污染标志置为 true新鲜橘子数量 - 1
for (int i 0; i 4; i) {int x pos.first dir_x[i];int y pos.second dir_y[i];if (x 0|| x nr || y 0|| y nc || grid[x][y] 0)continue;if (grid[x][y] 1) {hasPolluted true;--freshCount;grid[x][y] 2;q.push(make_pair(x, y));}if (freshCount 0) break;
} hasPolluted 用于表明当前层中是否至少有一个腐烂橘子造成了污染如果没有造成污染那么就要考虑是否无法污染所有新鲜橘子了。 class Solution {
public:int dir_x[4] {0, 1, 0, -1};int dir_y[4] {1, 0, -1, 0};int orangesRotting(vectorvectorint grid) {int nr grid.size();if (nr 0) return 0;int nc grid[0].size();int freshCount 0;queuepairint, int q;for (int i 0; i nr; i) {for (int j 0; j nc; j) {if (grid[i][j] 1) {freshCount;} else if (grid[i][j] 2) {q.push(make_pair(i, j));}}}int timeCount 0;int hasPolluted false;while (!q.empty()) {int currentSize q.size();for (int i 0; i currentSize; i) {pairint, int pos q.front();q.pop();for (int i 0; i 4; i) {int x pos.first dir_x[i];int y pos.second dir_y[i];if (x 0|| x nr || y 0|| y nc || grid[x][y] 0)continue;if (grid[x][y] 1) {hasPolluted true;--freshCount;grid[x][y] 2;q.push(make_pair(x, y));}if (freshCount 0) break;}}if (hasPolluted) timeCount;hasPolluted false;}return freshCount 0 ? timeCount : -1;}
};
技能点使用循环结构来测试上/下/左/右四个方位。
int dir_x[4] {0, 1, 0, -1};
int dir_y[4] {1, 0, -1, 0};for (int i 0; i 4; i) {int x pos.first dir_x[i];int y pos.second dir_y[i];if (x 0|| x nr || y 0|| y nc)// ...
} 并且用逆否命题来作为判断条件就不需要写很多 了
