你提供的 Go 语言代码是用于解决“腐烂橘子”问题,但在实现上有几个错误和潜在的问题。以下是主要问题及改正建议:
curOrigin
未被正确更新: 你声明了curOrigin
,但没有在循环中更新它的值以跟踪当前新腐烂橘子的数量。队列操作不正确: 在处理每个已腐烂橘子的周围时,你应该使用一个新的队列来存储新腐烂的橘子,而不是在原队列上添加,这样会导致无限循环。
位置坐标索引错误: 在计算新橘子的位置时,你用的是
pos[0]
两次,第二个应该是pos[1]
。时间计算逻辑: 每次你扩展 BFS 时不需要增加
totalTime
,而是应该在外层循环中判断是否有新腐烂的橘子,以此增加时间。终止条件检查: 返回结果部分要确保检查所有原始橘子的状态(未腐烂)。
下面是修正后的代码示例:
func orangesRotting(grid [][]int) int {
var totalOrigin, curOrigin, totalTime int
queue := make([][2]int, 0)
height := len(grid)
width := len(grid[0])
for i := 0; i < height; i++ {
for j := 0; j < width; j++ {
if grid[i][j] == 1 {
totalOrigin++
}
if grid[i][j] == 2 {
queue = append(queue, [2]int{i, j})
}
}
}
totalTime := -1 // 因为我们会先做一次加1,然后再加
for len(queue) > 0 {
size := len(queue)
totalTime++
for i := 0; i < size; i++ {
pos := queue[0]
queue = queue[1:]
dx := [4]int{1, -1, 0, 0}
dy := [4]int{0, 0, 1, -1}
for j := 0; j < 4; j++ {
tx := pos[0] + dx[j]
ty := pos[1] + dy[j]
if tx >= 0 && tx < height && ty >= 0 && ty < width && grid[tx][ty] == 1 {
grid[tx][ty] = 2 // 腐烂这个橘子
curOrigin++ // 新增一个已腐烂的橘子
queue = append(queue, [2]int{tx, ty})
}
}
}
}
// 检查是否所有的原始橘子都已经腐烂
if curOrigin != totalOrigin {
return -1
}
return totalTime
}
修改点:
- 使用变量
size
来记录当前队列长度,这样可以防止内部循环中对队列长度改变造成的问题。 - 移动增量到外部,使其更符合 BFS 的逻辑。
- 确保对横纵坐标分别处理,避免混淆。
- 最后对比总数与当前已腐烂数量返回最终结果。
请尝试上述代码并验证功能!
内容由零声教学AI助手提供,问题来源于学员提问