LeetCode——994.腐烂的橘子

通过万岁！！！

• 题目：就是给你一个二维数组，然后里面有0，1，2三种数，2每一分钟会将身边的1变为2。问需要多久，里面全是2。如果始终还有1，则返回-1。
• 思路：就是bfs即可，我们将所有的2都加入队列，然后每次遍历里面所有的2。去感染身边的1，每次遍历队列中的2，则时间就++。最后返回时间即可。这里有几个注意事项，就是我们初始化的时候，可以把1的个数统计出来，存在num中，这样每次感染一个，num–，最后如果num=0，则表示全部变坏，没有1了，否则就返回-1，因为还有1存在。并且如果我们最开始统计出来num就是0，则直接return0即可。
• 技巧：就是广度优先遍历。

java代码

class Solution {public int orangesRotting(int[][] grid) {int m = grid.length;int n = grid[0].length;int[][] dir = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};Queue<Point> queue = new LinkedList<>();int num = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == 2) {queue.add(new Point(i, j));}if (grid[i][j] == 1) {num++;}}}if (num == 0) return 0;int size, level = -1;while (!queue.isEmpty()) {level++;size = queue.size();Point remove;int nx, ny;for (int i = 0; i < size; i++) {remove = queue.remove();for (int j = 0; j < 4; j++) {nx = remove.x + dir[j][0];ny = remove.y + dir[j][1];if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 1) {grid[nx][ny] = 2;num--;queue.add(new Point(nx, ny));}}}}if (num > 0) return -1;return level;}class Point {int x, y;public Point(int x, int y) {this.x = x;this.y = y;}}
}

• 总结：题目BFS，然后加了一些判断。还是比较简单的，广度优先就是用来计算层数的。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！