当前位置：首页 > news >正文

LeetCode算法题(Go语言实现)_48

news 来源：原创 2025/8/27 0:14:25

题目

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，腐烂的橘子周围 4 个方向上相邻的新鲜橘子都会腐烂。
返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

一、代码实现（多源BFS）

func orangesRotting(grid [][]int) int {m, n := len(grid), len(grid[0])queue := [][2]int{}fresh := 0// 初始化队列并统计新鲜橘子数量for i := 0; i < m; i++ {for j := 0; j < n; j++ {if grid[i][j] == 2 {queue = append(queue, [2]int{i, j})} else if grid[i][j] == 1 {fresh++}}}if fresh == 0 {return 0}dirs := [4][2]int{{-1,0}, {1,0}, {0,-1}, {0,1}}time := 0for len(queue) > 0 {levelSize := len(queue)levelSpread := falsefor i := 0; i < levelSize; i++ {cell := queue[0]queue = queue[1:]for _, d := range dirs {x, y := cell[0]+d[0], cell[1]+d[1]if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 {grid[x][y] = 2fresh--queue = append(queue, [2]int{x, y})levelSpread = true}}}if levelSpread {time++}}if fresh > 0 {return -1}return time
}

二、算法分析

1. 核心思路

多源广度优先搜索：初始将所有腐烂橘子入队，同时进行层级扩散
层级时间统计：每完成一轮队列处理代表经过1分钟
新鲜橘子计数：实时更新剩余新鲜橘子数量，判断终止条件

2. 关键步骤

初始化阶段：
- 遍历网格收集腐烂橘子坐标
- 统计新鲜橘子总数fresh
- 特判无新鲜橘子时直接返回0
BFS扩散过程：
- 每次处理当前队列的所有节点（对应同一时间层级）
- 四个方向扩散，感染相邻新鲜橘子
- 维护levelSpread标志判断是否实际发生扩散
终止条件判断：
- 最终检查fresh是否为0
- 剩余新鲜橘子说明存在隔离区域

3. 复杂度

指标	值	说明
时间复杂度	O(m*n)	每个节点最多入队一次
空间复杂度	O(m*n)	队列最大存储所有腐烂橘子坐标

三、图解示例

在这里插入图片描述

四、边界条件与扩展

1. 特殊场景验证

全腐烂初始状态：返回0（如示例3）
隔离区域存在：返回-1（如示例2的角落橘子）
多源同时扩散：不同腐烂源并行加速感染

2. 扩展应用

动态障碍物：支持实时更新墙的位置重新计算
三维空间扩展：增加z轴方向扩散维度
感染概率模型：每次感染存在成功概率

3. 多语言实现

import java.util.LinkedList;
import java.util.Queue;public class Solution {public int orangesRotting(int[][] grid) {if (grid == null || grid.length == 0) {return -1;}int rows = grid.length;int cols = grid[0].length;int fresh = 0;Queue<int[]> queue = new LinkedList<>();// 初始化队列和新鲜橘子计数for (int r = 0; r < rows; r++) {for (int c = 0; c < cols; c++) {if (grid[r][c] == 2) {queue.offer(new int[]{r, c});} else if (grid[r][c] == 1) {fresh++;}}}// 如果没有新鲜橘子，直接返回0if (fresh == 0) {return 0;}int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};int minutes = 0;while (!queue.isEmpty() && fresh > 0) {int levelSize = queue.size();for (int i = 0; i < levelSize; i++) {int[] current = queue.poll();for (int[] dir : directions) {int nr = current[0] + dir[0];int nc = current[1] + dir[1];if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1) {grid[nr][nc] = 2;fresh--;queue.offer(new int[]{nr, nc});}}}if (!queue.isEmpty()) {minutes++;}}return fresh == 0 ? minutes : -1;}
}

from collections import dequedef orangesRotting(grid):if not grid:return -1rows = len(grid)cols = len(grid[0])fresh = 0queue = deque()# 初始化队列和新鲜橘子计数for r in range(rows):for c in range(cols):if grid[r][c] == 2:queue.append((r, c))elif grid[r][c] == 1:fresh += 1# 如果没有新鲜橘子，直接返回0if fresh == 0:return 0directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]minutes = 0while queue and fresh > 0:# 处理当前层的所有橘子level_size = len(queue)for _ in range(level_size):r, c = queue.popleft()for dr, dc in directions:nr, nc = r + dr, c + dcif 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:grid[nr][nc] = 2fresh -= 1queue.append((nr, nc))if queue:  # 只有这一层有橘子腐烂时才增加时间minutes += 1return minutes if fresh == 0 else -1

五、总结与优化

1. 算法对比

方法	优势	适用场景
BFS	保证最短时间	常规网格扩散问题
DFS	空间效率高	路径存在性验证
并查集	动态连接关系维护	需要持续更新感染关系

2. 工程优化

层级标记优化：使用轮次标记替代队列长度计算
内存压缩存储：用位运算记录感染状态
并行计算：多线程处理不同腐烂源扩散

3. 扩展方向

权重扩散：不同方向感染速度不同
抗感染机制：部分橘子具有抗感染能力
可视化模拟：生成感染过程动画演示

LeetCode算法题(Go语言实现)_48

题目在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一： 值 0 代表空单元格； 值 1 代表新鲜橘子； 值 2 代表腐烂的橘子。每分钟，腐烂的橘子周围 4 个方向上相邻的新鲜橘子都会腐烂。返回直到单元格中…...

编程日记 2025/8/27 0:14:25

ESP-ADF外设子系统深度解析：esp_peripherals组件架构与核心设计（核心API详解之单个外设管理）

目录单个外设管理APIesp_periph_createesp_periph_set_functionesp_periph_startesp_periph_stopesp_periph_set_dataesp_periph_get_dataesp_periph_get_stateesp_periph_get_idesp_periph_set_idesp_periph_initesp_periph_runesp_periph_destroy 单个外设管理API esp_peri…...

编程日记 2025/8/21 22:12:16

基于vue2+ElementUI的el-tree封装一个带搜索的树形组件

需求实现一个如图带搜索框的下拉树形组件。解决方案利用el-inputel-tree实现自定义带搜索的下拉树形组件。具体实现步骤 1、创建TreeSelect组件 <template><div class"tree-select-wrapper" v-clickoutside"handleClose"><el-inpu…...

编程日记 2025/8/27 0:13:24

G2学习打卡

🍨 本文为🔗365天深度学习训练营中的学习记录博客🍖 原作者：K同学啊 DCGAN实践 import torch, random, random, os import torch.nn as nn import torch.nn.parallel import torch.optim as optim import torch.utils.data im…...

编程日记 2025/8/22 18:22:03

【广州华锐互动】汽车生产引入数字孪生系统，优化生产流程，提升汽车产品质量

数字孪生系统的应用为企业带来了生产流程的革命性变革。以汽车制造企业为例，该企业在生产过程中引入数字孪生系统，实现了生产流程的全面优化和产品质量的显著提升。在生产流程优化方面，数字孪生系统对汽车生产线进行了全方位的模拟和实时…...

编程日记 2025/8/20 23:35:02

从Gradio App创建Discord Bot/Slack Bot/Website Widget（2）——从Gradio App创建Slack Bot

从Gradio App创建Discord Bot/Slack Bot/Website Widget（2）——从Gradio App创建Slack Bot 本篇摘要18. 从Gradio App创建Discord Bot/Slack Bot/Website Widget18.2 从Gradio App创建Slack Bot18.2.1 运作原理及前置条件1. 运作原理2. 前置条件 18.2.2 …...

编程日记 2025/8/22 15:54:39

基于STM32G474的SPI获取MT6816编码器绝对角度配置指南

前言：最近上手使用了一款编码器芯片，也是先艰难阅读了一下全英文版本的编码器的规格手册，然后通过SPI读取了一下绝对值角度。虽然发现使用起来还是挺简单的，但使用后还是会产生一个对其原理层面的好奇，比如磁编码器内部…...

编程日记 2025/8/20 15:30:32

深入学习ReentrantLock

ReentrantLock 0. 前言：为什么需要 ReentrantLock？1. 基础概念与核心特性1.1 什么是 ReentrantLock？1.2 ReentrantLock vs. synchronized1.3 核心特性详解1.3.1 可重入性 (Reentrancy)1.3.2 公平性选择 (Fairness Choice)1.3.3 可中断获取锁 …...

编程日记 2025/8/23 13:19:38

Spring Boot 集成金蝶 API 演示

✨ Spring Boot 集成金蝶 API 演示：登录 / 注销 Cookie 保存本文将通过 Spring Boot 完整实现一套金蝶接口集成模型，包括： ✅ 普通登录✅ AppSecret 登录✅ 注销✅ Cookie 保存与复用 📅 项目结构 src/ ├── controller/ │…...

编程日记 2025/8/24 16:16:31

适用于 HAL 的 AIDL

目录设计初衷注意编写AIDLHAL接口查找AIDLHAL接口扩展接口将现有HAL从HIDL转换为AIDL AIDL与HIDL之间的主要差异针对HAL的供应商测试套件（VTS）测试 Android 11 中引入了在 Android 中使用 AIDL 实现 HAL 的功能，从而可以在不使用 HIDL 的情况下实现 Android 的部分…...

编程日记 2025/8/26 4:34:39

49、Spring Boot 详细讲义（六）（SpringBoot2.x整合Mybatis实现CURD操作和分页查询详细项目文档）

项目文档：银行借据信息CURD操作和分页查询一、项目概述 1. 项目简介本项目旨在使用Spring Boot框架整合MyBatis连接Mysql数据库实现借据信息的增加、删除、修改和查询功能，同时支持分页查询，并提供对应的Restful风格的接口。 2.环境准备 2.1.工具和软件准备 JDK（建议…...

编程日记 2025/8/25 14:21:42

C# 运行web项目

1、web项目直接点击顶部运行...

编程日记 2025/8/17 18:44:39

GPU服务器声音很响可以怎么处理

当GPU服务器运行时噪音过大，通常是由于高负载下散热风扇高速运转所致。以下是分步骤的解决方案，帮助您有效降低噪音并保持设备稳定运行： 一、排查噪音来源定位声源 • 使用声级计或手机分贝检测APP，确定最大噪音位置&#xff0…...

编程日记 2025/8/19 8:18:09

Java如何选择ojdbc驱动

如何选择ojdbc驱动？ 取决于短板。如果JDK版本高，数据库版本低，根据Oracle数据库版本选择。如果JDK版本低，数据库版本高，根据Java版本选择。 Oracle官网OJDBC驱动和受支持的JDK版本 23ai 21c 19c 驱动类型选择 oj…...

编程日记 2025/8/24 11:56:23

【微思就业推荐】T岗位-北京，福州，厦门等地

到微思学习，免费推荐就业！学员内推！ 原创厦门微思网络 2025年04月有哪些大公司在招OCP认证人才？ 有哪些大公司在招聘拥有HCIE认证的人才 ① 委托单位：润欣商业管理(厦门)有限公司央企-华润资产的子公司岗位&am…...

编程日记 2025/8/26 1:27:37

Linux 命令全解析：从零开始掌握 Linux 命令行

Linux 作为一款强大的开源操作系统，广泛应用于服务器、嵌入式系统以及超级计算机领域。掌握 Linux 命令行技能，是每一位开发者和系统管理员的必备能力。本文将从基础开始，为你详细介绍常用的 Linux 命令，以及它们的使用场景和示例…...

编程日记 2025/8/20 19:26:57

2025年4月份生活有感

今天在5000B培训的下午，一起入所来的小伙伴，有个申请了深圳大学的博士，已录取。哎，想起了当年申博时候信心和决心不足，导致后面匆匆的拿了offer去工作。看到同事的选择还是非常羡慕，想到自己5月份的婚礼&am…...

编程日记 2025/8/23 11:51:26

鸿蒙系统开发状态更新字段区别对比

在鸿蒙系统开发中，状态管理是构建响应式UI的核心机制，主要通过装饰器（Decorators）实现字段的状态观测与更新。根据鸿蒙的版本（V1稳定版和V2试用版），支持的装饰器及其特性有所不同。以下是主要状…...

编程日记 2025/8/26 7:58:19

CEPH OSD_SLOW_PING_TIME_FRONT/BACK 警告处理

ceph config set mgr mon_warn_on_slow_ping_time 2000说明：mon_warn_on_slow_ping_time 该值默认为0，那么只要 osd 心跳超过 mon_warn_on_slow_ping_ratio of osd_heartbeat_grace. 也就是超过 mon_warn_on_slow_ping_ratio和mon_warn_on_slow_ping_rat…...

编程日记 2025/8/20 10:52:43

HTML应用指南：利用POST请求获取全国小菜园门店位置信息

小菜园作为一家以徽菜为主的快餐品牌，自2013年成立以来，凭借其独特的烹饪理念和精致的东方口味菜品，在中国市场上迅速崛起。该品牌强调少油少盐、减少调味品使用，旨在传承并发扬徽州风味的独特魅力。这种健康且不失美味的烹饪方式…...

编程日记 2025/8/26 15:49:28

Python在去中心化物联网中的应用：数据安全、智能合约与边缘计算的融合

Python在去中心化物联网中的应用：数据安全、智能合约与边缘计算的融合在万物互联的时代，传统物联网（IoT）架构依赖于集中式服务器来管理数据、设备互联与身份认证。然而，随着设备数量激增，中心化架构的可扩展性、安全性和隐私问题逐渐暴露。去中心化物联网（DeIoT）通过…...

编程日记 2025/8/21 7:35:12

CEPH配置优化建议

一、硬件配置优化磁盘选择： SSD 与 HDD 搭配：使用 SSD 作为 OSD 日志盘（Journal）或元数据存储，HDD 作为数据盘。推荐 SSD 与 HDD 的比例为 1:3~5，具体根据业务负载调整。 RAID 禁用：避免使用硬…...

编程日记 2025/8/25 18:33:23

深度学习入门：神经网络的学习

目录 1 从数据中学习1.1 数据驱动1.2 训练数据和测试数据 2损失函数2.1 均方误差2.2 交叉熵误差2.3 mini-batch学习2.4 mini-batch版交叉熵误差的实现2.5 为何要设定损失函数 3 数值微分3.1 数值微分3.3 偏导数 4 梯度4.1 梯度法4.2 神经网络的梯度 5 学习算法的实现5.1 2层神经…...

编程日记 2025/8/22 12:27:10

机器学习_决策树

决策树的特点可以处理非线性的问题可解释强，没有θ模型简单，模型预测效率高 if else不容易显示的使用函数表达，不可微决策树的生成和预测生成：通过大量数据生成一颗非常好的树，用这棵树来预测新来的数据。预测&…...

编程日记 2025/8/17 13:23:44

深入理解UML动态图：系统行为建模全景指南

目录前言1. 动态图概述2. 用例图（Use Case Diagram）2.1 定义与作用2.2 应用价值2.3 实践建议 3. 顺序图（Sequence Diagram）3.1 定义与特征3.2 应用优势3.3 建模建议 4. 活动图（Activity Diagram）4.1 定义与…...

编程日记 2025/8/24 21:19:23

Linux驱动开发进阶（九）- SPI子系统BSP驱动

文章目录 1、前言2、SPI总线注册3、SPI设备注册4、SPI驱动注册5、SPI BSP驱动 1、前言学习参考书籍以及本文涉及的示例程序：李山文的《Linux驱动开发进阶》本文属于个人学习后的总结，不太具备教学功能。 2、SPI总线注册驱动源码文件：dri…...

编程日记 2025/8/25 17:38:17

wabpack学习记录

wabpack学习记录前言项目写了不少对webpack了解甚少只记住一些必要的概念以及指令所以像深究一下具体是什么可以做什么如何做等 package.json 文件详解 name: 项目的名称。 version: 项目的版本号。 description: 项目的描述。 author: 项目的作者或维护者信息。 l…...

编程日记 2025/8/26 8:17:32

计算机视觉——基于 Yolov8 目标检测与 OpenCV 光流实现目标追踪

1. 概述目标检测（Object Detection）和目标追踪（Object Tracking）是计算机视觉中的两个关键技术，它们在多种实际应用场景中发挥着重要作用。目标检测指的是在静态图像或视频帧中识别出特定类别的目标对象&#xff0…...

编程日记 2025/8/17 18:46:02

React 更新 state 中的数组

更新 state 中的数组数组是另外一种可以存储在 state 中的 JavaScript 对象，它虽然是可变的，但是却应该被视为不可变。同对象一样，当你想要更新存储于 state 中的数组时，你需要创建一个新的数组（或者创建一份已有数组…...

编程日记 2025/8/22 12:36:55

[250415] OpenAI 推出 GPT-4.1 系列，支持 1M token

目录 OpenAI 推出 GPT-4.1 系列 OpenAI 推出 GPT-4.1 系列 OpenAI 宣布，新一代 GPT-4.1 模型系列正式发布，包括 GPT-4.1, GPT-4.1 mini 和 GPT-4.1 nano 三款模型，该系列模型在各项性能指标上全面超越 GPT-4o 和 GPT-4o mini，尤其…...

编程日记 2025/8/22 19:43:47

分布式锁+秒杀异步优化

文章目录问题思路setnx实现锁误删问题和解决方案Redis Lua脚本问题引出解决方案 setnx实现的问题Redission快速入门redission可重入锁原理秒杀优化(异步优化)异步秒杀思路秒杀资格判断Redis消息队列问题比如我们两个机器都部署了我们项目，这里nginx使用轮询的方…...

编程日记 2025/8/20 18:21:15

数据服务化 VS 数据中台：战略演进中的价值重构

在企业数据战略的演进历程中，数据中台曾被视为解决数据孤岛的 “万能钥匙”，而数据服务化的兴起则标志着企业从 “数据资源囤积” 向 “数据价值释放” 的深刻转型。两者的核心差异不仅在于技术架构，更在于对数据资产的定位与使用理念的根本分…...

编程日记 2025/8/20 8:31:35

PL/SQL登录慢，程序连接Oracle 提示无法连接或无监听

PL/SQL登录慢，程序连接Oracle 提示无法连接或无监听错误提示：ORA-12541: TNS: 无监听程序的解决办法， 现象：PL/SQL登录慢，程序连接Oracle 提示无法连接或无监听监听已经正常开起，但还是PL/SQL登录慢或…...

编程日记 2025/8/23 16:44:51

【JAVAFX】自定义FXML 文件存放的位置以及使用

情况 1：FXML 文件与调用类在同一个包中（推荐） 假设类 MainApp 的包是 com.example，且 FXML 文件放在 resources/com/example 下： 项目根目录 ├── src │ └── sample │ └── Main.java ├── src/s…...

编程日记 2025/8/26 22:18:26

DDoS(分布式拒绝服务)攻击

DDoS(分布式拒绝服务)攻击这是一份全面系统的 DDoS（分布式拒绝服务攻击）知识总结，适合用于学习、报告、讲稿或者面试准备。内容涵盖定义、原理、危害、利用、工具、防护策略等。一、什么是DDoS DDoS（Distributed Denial of Se…...

编程日记 2025/8/19 21:42:24

scikit-learn初探

KFold k交叉验证，k-1个作为训练集，剩下的作为测试集 split split(X, yNone, groupsNone)X： (n_samples, n_features)的矩阵，行数为n_samples，列数为n_features y：(n_samples,)为列向量，表示监…...

编程日记 2025/8/26 11:41:50

深入解析 sklearn 中的多种特征编码方式：功能、适用场景与选择建议

标题：深入解析 sklearn 中的多种特征编码方式：功能、适用场景与选择建议摘要： 在机器学习中，特征编码是数据预处理的重要环节，直接影响模型的性能和效果。本文详细介绍了 sklearn 及其生态中（含第三方库…...

编程日记 2025/8/23 12:14:59

windows10 wsl2 安装ubuntu和docker

见弃用Docker Desktop：在WSL2中玩转Docker之Docker Engine 部署与WSL入门-阿里云开发者社区如果启动docker时报下面这个错， 那是因为systemctl没有启用 sudo systemctl start docker System has not been booted with systemd as init system (PID 1)…...

编程日记 2025/8/20 15:35:47

一文读懂WPF系列之依赖属性与附加属性

依赖属性与附加属性依赖属性对比C#属性WPF依赖属性（Dependency Properties）优先级计算与值决策回调与验证机制WPF 自带的依赖属性自定义依赖属性附加属性本质与定义与依赖属性的区别附加属性的典型应用场景自定义附加属性注意事项属性…...

编程日记 2025/8/17 21:27:37

1×1卷积与GoogleNet

11卷积卷积核的尺寸等于1的卷积核 11卷积有什么用 1. 通道混合与特征转换背景：在卷积神经网络中，输入数据通常有多个通道（例如RGB图像有3个通道，经过卷积层后通道数可能会增加）。不同通道的特征图可能包含了不同的…...

编程日记 2025/8/25 7:27:46

Handsontable 表格组件的使用

文章目录 1. 安装 Handsontable2. 创建一个基本表格3. 主要配置3.1、 data 数据3.2、 columns 指定列配置 4. Handsontable 高级功能4.1、添加排序4.2、过滤数据4.3、选中行高亮4.4、只读单元格4.5、校验数据 5. Handsontable 与 Vue结合6. 总结 Handsontable 是一个强大的…...

编程日记 2025/8/26 18:50:22

消息中间件面试题

前言本章内容来自B站黑马程序员java大厂面试题与小林coding 如有侵权立即删除博主学习笔记，如果有不对的地方，海涵。如果这篇文章对你有帮助，可以点点关注，点点赞，谢谢你！ 1.通用篇 1.1 什么是消息…...

编程日记 2025/8/20 21:24:44

数据结构与算法--1.判断数组中元素是否有重复

在C语言中，我们可以使用类似的方法来实现判断数组中是否有重复值的功能。由于C语言没有内置的哈希集合（如Python的set或C的unordered_set），我们需要自己实现一个简单的哈希表或使用其他方法。方法一：暴力法&#xff…...

编程日记 2025/8/26 22:41:10

硬件工程师面试常见问题（1）

第一问：单片机上电后没有运转，首先要检查什么？ （1）单片机供电是否正常& 电路焊接检查用万用表测量对应引脚的供电电压，检查对不对。 （2）单片机复位是否释放用万用表测量复位引…...

编程日记 2025/8/23 17:18:31

测试100问：web测试和APP测试的区别

哈喽，大家好，我是十二，那今天要为大家分享的是高频面试题：web测试和 App测试的区别。从功能测试方面来讲，web测试和 App测试在测试的流程以及测试用例的设计上是没有区别的，那主要的区别包含以下三个方面&…...

编程日记 2025/8/26 20:47:26

Leetcode 3518. Smallest Palindromic Rearrangement II

Leetcode 3518. Smallest Palindromic Rearrangement II 1. 解题思路2. 代码实现题目链接：Leetcode 3518. Smallest Palindromic Rearrangement II 1. 解题思路这一题是题目Leetcode 3517. Smallest Palindromic Rearrangement I的升级版本，其主要的…...

编程日记 2025/8/25 10:23:40