0%

LeetCode 994.腐烂的橘子

解法一,直接暴力。假设网格两个边长分别为 nm ,复杂度 O(n*m*max(n, m))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public int orangesRotting(int[][] grid) {
int n = grid.length, m = grid[0].length;
int cnt = 0, ans = 0;
int vis[][] = new int[n][m];
while(true) {
int cur = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(grid[i][j] == 1) cur++;
}
}

if(cnt == 0) ans = cur;
else {
if(ans == cur) return -1;
else ans = cur;
}

if(ans == 0) return cnt;

for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(grid[i][j] == 2 && vis[i][j] == cnt) {
if(i - 1 >= 0 && grid[i - 1][j] == 1) {
grid[i - 1][j] = 2;
vis[i - 1][j] = cnt + 1;
}
if(j - 1 >= 0 && grid[i][j - 1] == 1) {
grid[i][j - 1] = 2;
vis[i][j - 1] = cnt + 1;
}
if(i + 1 < n && grid[i + 1][j] == 1) {
grid[i + 1][j] = 2;
vis[i + 1][j] = cnt + 1;
}
if(j + 1 < m && grid[i][j + 1] == 1) {
grid[i][j + 1] = 2;
vis[i][j + 1] = cnt + 1;
}
}

}
}
cnt++;
}
}
}

解法二,广度优先搜索。

  • 先找出腐烂的橘子,添加进 queue 中。
  • 队列 queue只让腐烂的橘子入队;
  • 出队时,让当前腐烂橘子四周的新鲜橘子都变为腐烂,即 grid[newX][newY] = 2
  • minute 记录腐烂的持续时间,每一层的橘子在内一层的橘子的腐烂时间基础之上自增 1,代表时间过了 1 分钟。
  • 最后检查网格中是否还有新鲜的橘子:
    • 有,返回 -1 代表 impossible
    • 没有则返回 minute
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Pos{
int x, y, minute;
public Pos(int _x, int _y, int _minute) {
x = _x;
y = _y;
minute = _minute;
}
}

class Solution {

static int[][] dir = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};

public int orangesRotting(int[][] grid) {
Queue<Pos> queue = new LinkedList<>();
int n = grid.length, m = grid[0].length;
int minute = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(grid[i][j] == 2) {
queue.add(new Pos(i, j, minute));
}
}
}
while(!queue.isEmpty()) {
Pos cur = queue.poll();
minute = cur.minute;
for(int i = 0; i < 4; i++) {
int newX = cur.x + dir[i][0];
int newY = cur.y + dir[i][1];
if(newX >= 0 && newX < n && newY >= 0 && newY < m && grid[newX][newY] == 1) {
queue.add(new Pos(newX, newY, minute + 1));
grid[newX][newY] = 2;
}
}
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(grid[i][j] == 1) return -1;
}
}
return minute;
}
}

理论上讲解法二应该比解法一速度快,但是在leetcode上解法二用的时间更多,很奇怪。

如果对您有帮助,请我喝杯奶茶?