网站制作多少钱资讯,东莞市住建局网,网站建设业务员怎么着客户,网站建设微信小程序开发阅读目录 1. 题目2. 解题思路3. 代码实现 1. 题目 2. 解题思路
1.记录下初始新鲜橘子的位置到 notRotting#xff0c;我们按照行把二维数组拉成一维#xff0c;所以#xff0c;一个vector 就可以实现了#xff1b;2.如果没有新鲜橘子#xff0c;那么第 0 分钟所有橘子已经… 阅读目录 1. 题目2. 解题思路3. 代码实现 1. 题目 2. 解题思路
1.记录下初始新鲜橘子的位置到 notRotting我们按照行把二维数组拉成一维所以一个vector 就可以实现了2.如果没有新鲜橘子那么第 0 分钟所有橘子已经腐烂直接返回3.如果有新鲜橘子那么我们遍历每一个新鲜橘子查看它的上下左右是否有腐烂的橘子如果有代表这一分钟这个新鲜橘子会被腐烂记录到 cur_Rotting否则这一分钟这个橘子仍然保持新鲜记录到 cur_notRotting4.遍历完后分钟数增加 1然后我们把这一分钟腐烂的橘子对应的位置置为 2;5.如果这一分钟之后没有腐烂的橘子总数没有变化也就是没有橘子被腐蚀那么跳出循环因为余下的没有腐烂的橘子永远也不会腐烂了6.如果这一分钟有橘子被腐烂那么更新未被腐烂的橘子cur_notRotting 到 notRotting重复步骤 3-67.如果notRotting为空代表所有橘子都被腐烂返回分钟数否则有橘子不会被腐烂返回-1
3. 代码实现
class Solution {
public:int orangesRotting(vectorvectorint grid) {int row grid.size();int col grid[0].size();vectorint notRotting;// 记录初始未腐烂的橘子位置for (int i 0; i row; i) {for (int j 0; j col; j) {if (grid[i][j] 1) {notRotting.push_back(i * col j);}}}if (notRotting.empty()) {return 0;}int minute 0;while (!notRotting.empty()) {vectorint cur_notRotting; // 这一分钟仍然没有腐烂的橘子vectorint cur_Rotting; // 这一分钟腐烂的橘子for (int k 0; k notRotting.size(); k) {int i notRotting[k] / col;int j notRotting[k] % col;// 上下左右有腐烂的橘子那么这个新鲜橘子会被腐烂if (i-1 0 grid[i-1][j] 2) {cur_Rotting.push_back(notRotting[k]);continue;}if (i1 row grid[i1][j] 2) {cur_Rotting.push_back(notRotting[k]);continue;}if (j-1 0 grid[i][j-1] 2) {cur_Rotting.push_back(notRotting[k]);continue;}if (j1 col grid[i][j1] 2) {cur_Rotting.push_back(notRotting[k]);continue;}// 否则这个橘子继续保持新鲜cur_notRotting.push_back(notRotting[k]);}// 这一分钟腐烂的橘子更新状态for (int k 0; k cur_Rotting.size(); k) {int i cur_Rotting[k] / col;int j cur_Rotting[k] % col;grid[i][j] 2;}minute 1;// 这一分钟没有橘子被腐烂跳出循环if (cur_notRotting.size() notRotting.size()) {break;}// 更新未腐烂橘子的位置notRotting cur_notRotting;}if (!notRotting.empty()) {return -1;} else {return minute;}}
};时间复杂度为 O ( m n ) O(mn) O(mn)空间复杂度为 O ( m n ) O(mn) O(mn)。
