英文:
Rotten Oranges LeetCode
问题
我正在尝试解决这个问题：https://leetcode.com/problems/rotting-oranges/
这个链接用图示解释得更清楚，但基本上你需要使每个与“腐烂”橙子（值为2）相邻的橙子也变为腐烂。
我使用广度优先搜索（BFS）来解决这个问题。首先，我创建一个队列来存储所有腐烂的橙子，然后将其传递给我的BFS函数，该函数检查是否可以向上/下/左/右移动，如果可以，则将其添加到队列中并更改值以表示该节点已被访问。
我的解决方案没有给出正确的答案，我不确定逻辑错误在哪里。
class Solution {
public int orangesRotting(int[][] grid) {
// 将所有值为2的橙子放入队列
// 遍历队列中的橙子，使周围的橙子变为腐烂
// 再次遍历整个网格 --> 任何不为2的橙子，返回-1
// 否则返回计数
Queue<String> q = new LinkedList<>();
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
if (grid[i][j] == 2) {
q.add("" + i + j);
}
}
}
int count = getMinutes(grid, q);
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
if (grid[i][j] == 1) {
return -1;
}
}
}
return count;
}
public static int getMinutes(int[][] grid, Queue<String> q) {
Queue<String> rotten = new LinkedList<>();
int count = 0;
final int[][] SHIFTS = {
{1, 0},
{-1, 0},
{0, 1},
{0, -1}
};
while (true) {
while (!q.isEmpty()) {
String s = q.remove();
int i = Integer.parseInt(s.substring(0, s.length() - 1));
int j = Integer.parseInt(s.substring(s.length() - 1));
for (int[] points : SHIFTS) {
int tempI = i + points[0];
int tempJ = j + points[1];
if (isValidMove(grid, tempI, tempJ)) {
rotten.add("" + tempI + tempJ);
grid[tempI][tempJ] = 2; // 标记为已访问
}
}
}
if (rotten.isEmpty()) {
return count;
}
count++;
q = rotten;
}
}
public static boolean isValidMove(int[][] grid, int i, int j) {
if (i < 0 || i >= grid.length || j < 0 || j >= grid[i].length || grid[i][j] != 1) {
return false;
}
return true;
}
}
英文:
I'm trying to solve this problem: https://leetcode.com/problems/rotting-oranges/
The link explains better than I can with the visuals, but basically you have to make every orange that's next to a "rotten" one (value 2) rotten as well.
I'm approaching this using a BFS. I start by making a queue for all the rotten oranges, then I pass that to my bfs function which checks if going (up/down/left/right) is possible and if it is then adds that to the queue and changes the value to show the node has already been visited.
My solution is not giving me the right answer and I'm not sure where the logical misstep is.
class Solution {
public int orangesRotting(int[][] grid) {
//get all 2's into a queue
//iterate over 2 making all oranges rotten
//iterate grid again --> anything that's not 2, return -1
//else return count
Queue<String> q = new LinkedList<>();
for(int i = 0; i < grid.length; i++) {
for(int j = 0; j < grid[i].length; j++) {
if(grid[i][j] == 2) {
q.add("" + i + j);
}
}
}
int count = getMinutes(grid, q);
for(int i = 0; i < grid.length; i++) {
for(int j = 0; j < grid[i].length; j++) {
if(grid[i][j] == 1) {
return -1;
}
}
}
return count;
}
public static int getMinutes(int[][] grid, Queue<String> q) {
Queue<String> rotten = new LinkedList<>();
int count = 0;
final int[][] SHIFTS = {
{1,0},
{-1,0},
{0,1},
{0,-1}
};
while(true) {
while(!q.isEmpty()) {
String s = q.remove();
int i = Integer.parseInt(s.substring(0, s.length() - 1));
int j = Integer.parseInt(s.substring(s.length() - 1));
for(int[] points : SHIFTS) {
int tempI = i + points[0];
int tempJ = j + points[1];
if(isValidMove(grid, tempI, tempJ)) {
rotten.add("" + tempI + tempJ);
grid[tempI][tempJ] = 2; //it's visited
}
}
}
if(rotten.isEmpty()) {
return count;
}
count++;
q = rotten;
}
}
public static boolean isValidMove(int[][] grid, int i, int j) {
if(i < 0 || i >= grid.length || j < 0 || j >= grid[i].length || grid[i][j] != 1) {
return false;
}
return true;
}
}
</details>
# 答案1
**得分**: 3
- 我建议你不要这样做：`q.add("" + i + j);` 如何区分`{11,2}`和`{1, 12}`，它们都会得到相同的字符串`"112"`？只需使用`q.add( new int[]{i, j} )`，这不应该会造成太大的性能问题，它们只是整数。实际上情况恰恰相反，这样会更快。
- 现在谈谈主要问题，你的算法几乎是正确的，除了一个问题，就是你需要在`while ( true )`内部初始化一个新的队列，因为每次清空当前队列时都必须从新的队列开始。思路是从一开始就有一队已经腐烂的橙子。让它们周围的橙子腐烂，并建立一个由新腐烂的橙子组成的新队列。然后重复，直到你的新的新腐烂橙子队列为空为止。因此，每次从已经腐烂的橙子开始时，都必须是一个新的队列。
修正了主要问题的`getMinutes`如下：
```java
public static int getMinutes(int[][] grid, Queue<String> q) {
int count = 0;
final int[][] SHIFTS = {
{1,0},
{-1,0},
{0,1},
{0,-1}
};
while(true) {
Queue<String> rotten = new LinkedList<>();
while(!q.isEmpty()) {
String s = q.remove();
int i = Integer.parseInt(s.substring(0, s.length() - 1));
int j = Integer.parseInt(s.substring(s.length() - 1));
for(int[] points : SHIFTS) {
int tempI = i + points[0];
int tempJ = j + points[1];
if(isValidMove(grid, tempI, tempJ)) {
rotten.add("" + tempI + tempJ);
grid[tempI][tempJ] = 2; //it's visited
}
}
}
if(rotten.isEmpty()) {
return count;
}
count++;
q = rotten;
}
}
英文:
-
I suggest you don't do this :
q.add("" + i + j);How would you distinguish between{11,2}and{1, 12}, both give the same string"112"? Just useq.add( new int[]{i, j} )it shouldn't cause too much of a performance problem they are just ints. In fact its the other way around. It should be faster. -
Now coming to the main issue, your algorithm is almost correct except for the fact that you need to initialize a new Queue inside
while ( true )because you have to start with a new queue every time you flush your current queue. The idea is you start with a queue of already rotten oranges. Rot their neighboring oranges and build a new queue consisting of the newly rotten oranges. Then repeat until your new queue of newly rotten oranges is empty. So it has to be a new queue everytime you start with already rotten oranges.
The modified getMinutes with the correction of the main issue is :
public static int getMinutes(int[][] grid, Queue<String> q) {
int count = 0;
final int[][] SHIFTS = {
{1,0},
{-1,0},
{0,1},
{0,-1}
};
while(true) {
Queue<String> rotten = new LinkedList<>();
while(!q.isEmpty()) {
String s = q.remove();
int i = Integer.parseInt(s.substring(0, s.length() - 1));
int j = Integer.parseInt(s.substring(s.length() - 1));
for(int[] points : SHIFTS) {
int tempI = i + points[0];
int tempJ = j + points[1];
if(isValidMove(grid, tempI, tempJ)) {
rotten.add("" + tempI + tempJ);
grid[tempI][tempJ] = 2; //it's visited
}
}
}
if(rotten.isEmpty()) {
return count;
}
count++;
q = rotten;
}
}
答案2
得分: 0
-
我的猜测是，如果没有早期的
freshOranges，你的解决方案可能缺少return 0。 -
这实际上是一个广度优先搜索算法，尽管为了懒惰的目的，将其压缩成一个函数中 ( ˆ_ˆ )：
public class Solution {
private static final int[][] directions = new int[][] {
{1, 0},
{-1, 0},
{0, 1},
{0, -1}
};
public static final int orangesRotting(int[][] grid) {
final int rows = grid.length;
final int cols = rows > 0 ? grid[0].length : 0;
if (rows == 0 || cols == 0) {
return 0;
}
Queue<int[]> queue = new LinkedList<>();
int freshOranges = 0;
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
if (grid[row][col] == 2) {
queue.offer(new int[] {row, col});
} else if (grid[row][col] == 1) {
freshOranges++;
}
}
}
if (freshOranges == 0) {
return 0;
}
int count = 0;
while (!queue.isEmpty()) {
count++;
final int size = queue.size();
for (int i = 0; i < size; i++) {
final int[] cell = queue.poll();
for (int[] direction : directions) {
final int row = cell[0] + direction[0];
final int col = cell[1] + direction[1];
if (
row < 0 ||
col < 0 ||
row >= rows ||
col >= cols ||
grid[row][col] == 0 ||
grid[row][col] == 2
) {
continue;
}
grid[row][col] = 2;
queue.offer(new int[] {row, col});
freshOranges--;
}
}
}
return freshOranges == 0 ? count - 1 : -1;
}
}
英文:
Looks pretty good!
-
My guess is that your solution is missing
return 0for if there is nofreshOrangesearly. -
This is similarly a Breadth First Search algorithm, crammed into one function though for laziness purposes ( ˆ_ˆ ):
public class Solution {
private static final int[][] directions = new int[][] {
{1, 0},
{ -1, 0},
{0, 1},
{0, -1}
};
public static final int orangesRotting(
int[][] grid
) {
final int rows = grid.length;
final int cols = rows > 0 ? grid[0].length : 0;
if (rows == 0 || cols == 0) {
return 0;
}
Queue<int[]> queue = new LinkedList<>();
int freshOranges = 0;
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
if (grid[row][col] == 2) {
queue.offer(new int[] {row, col});
} else if (grid[row][col] == 1) {
freshOranges++;
}
}
}
if (freshOranges == 0) {
return 0;
}
int count = 0;
while (!queue.isEmpty()) {
count++;
final int size = queue.size();
for (int i = 0; i < size; i++) {
final int[] cell = queue.poll();
for (int[] direction : directions) {
final int row = cell[0] + direction[0];
final int col = cell[1] + direction[1];
if (
row < 0 ||
col < 0 ||
row >= rows ||
col >= cols ||
grid[row][col] == 0 ||
grid[row][col] == 2
) {
continue;
}
grid[row][col] = 2;
queue.offer(new int[] {row, col});
freshOranges--;
}
}
}
return freshOranges == 0 ? count - 1 : -1;
}
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论