ZBLOG

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++ { ...

你提供的 Go 语言代码是用于解决“腐烂橘子”问题,但在实现上有几个错误和潜在的问题。以下是主要问题及改正建议:

  1. curOrigin 未被正确更新: 你声明了 curOrigin,但没有在循环中更新它的值以跟踪当前新腐烂橘子的数量。

  2. 队列操作不正确: 在处理每个已腐烂橘子的周围时,你应该使用一个新的队列来存储新腐烂的橘子,而不是在原队列上添加,这样会导致无限循环。

  3. 位置坐标索引错误: 在计算新橘子的位置时,你用的是 pos[0] 两次,第二个应该是 pos[1]

  4. 时间计算逻辑: 每次你扩展 BFS 时不需要增加 totalTime,而是应该在外层循环中判断是否有新腐烂的橘子,以此增加时间。

  5. 终止条件检查: 返回结果部分要确保检查所有原始橘子的状态(未腐烂)。

下面是修正后的代码示例:

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助手提供,问题来源于学员提问

本站部分文章来源于网络,版权归原作者所有,如有侵权请联系站长删除。
转载请注明出处:https://golang.0voice.com/?id=20468

分享:
扫描分享到社交APP
上一篇
下一篇
发表列表
游客 游客
此处应有掌声~
评论列表

还没有评论,快来说点什么吧~

联系我们

在线咨询: 点击这里给我发消息

微信号:3007537140

上班时间: 10:30-22:30

关注我们
x

注册

已经有帐号?