大家好，我就是那个在B站讲算法的「华南溜达虎」。
大家都知道有些字节的员工去哪都喜欢戴着工牌，有同学解释到因为吃饭、门禁等都需要工牌，只是为了方便才戴的。不过这个理由貌似没有说服力，刚好今天看到一位同学吐槽字节的工牌，分享给大家，纯粹娱乐一下。这位同学说拿到字节的工牌直接就成了宇宙霸主，耶稣见了都得磕头念叨一句皇上吉祥。
评论区的同学纷纷开启段子模式，一位同学说上次回家给老祖宗上坟，由于年代久远找不到坟头，于是掏出字节的工牌，只见远处一股浓浓的青烟冒出，于是找到了祖坟。还有一位同学说去参观金字塔，直接拿出字节的工牌刷了一下，门就开了。工牌，文化衫等确实成为大厂光环的一种表现形式，不止国内，前几天看到一位国外的博主分享说英伟达的文化衫在相亲市场比劳力士的手表还好用。
25届秋招已经开始了，我组织了一个秋招群，大家可以交流学习心得、面试经验，分享工作机会，有啥问题也可以在群里咨询。在群里我整理了一百多家已经启动秋招企业的文档，以及投递入口，每天都会更新，大家只要按照这个文档海投就可以了。
大家互帮互助相信一定可以拿下秋招！计算机相关专业的同学可以 点击底部的「阅读原文」 加群。
言归正传，今天我们来分享一道高频面试题「腐烂的橘子」。
题目描述
在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
值 0 代表空单元格；值 1 代表新鲜橘子；值 2 代表腐烂的橘子。每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
举个例子：
输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
输出：4
思路解析
因为橘子每分钟会向四周扩散腐烂，而且可能从多个网格同时开始腐烂。这种一层一层的腐烂跟广度优先搜索的过程非常类似，我们可以使用广度优先搜索来模拟橘子腐烂的过程。
步骤如下：
把所有腐烂橘子对应的坐标存到队列里面。 计算当前队列中橘子的数量为 n，队列中这n个橘子依次弹出队列，并把与这些腐烂橘子相邻的新鲜橘子改为腐烂的橘子，放到队列中。这里是模拟与腐烂橘子相邻的新鲜橘子同时腐烂的过程，完成这个过程相当于只花了一分钟。重复 步骤2直到队列为空或者新鲜橘子的数量为0。最后如果还有新鲜橘子就返回-1，否则返回整个过程使用的时间。
下面我们给出c++和python两种代码实现。
c++代码
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
//队列用来保存腐烂橘子在网格中的坐标
queue<pair<int, int>> q;
//time用来保存所用的时间，fresh用来保存新鲜橘子的个数
int time = 0, fresh = 0;
int rows = grid.size();
int cols = grid[0].size();
for (int r = 0; r < rows; ++r) {
for (int c = 0; c < cols; ++c) {
// 统计新鲜橘子的数量
if (grid[r][c] == 1)
++fresh;
// 把腐烂的橘子的坐标放到队列中
if (grid[r][c] == 2)
q.push({r,c});
}
}
//腐烂橘子扩散的四个方向
vector<pair<int, int>> dirs = {{1,0}, {-1,0}, {0,1}, {0,-1}};
while (!q.empty() && fresh > 0) {
int q_len = q.size();
for (int i = 0; i < q_len; ++i) {
auto cur = q.front();
q.pop();
for (auto dir : dirs) {
int row = cur.first + dir.first;
int col = cur.second + dir.second;
if (row < 0 || row >= rows || col < 0 || col >= cols || grid[row][col] != 1)
continue;
grid[row][col] = 2;
q.push({row, col});
--fresh;
}
}
//紧邻腐烂橘子的一层新鲜橘子变腐烂，更新使用的时间
++time;
}
//最后还有新鲜的橘子返回-1
if (fresh)
return -1;
else
return time;
}
};
python代码
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
# 队列用来保存腐烂橘子在网格中的坐标
q = deque()
# time用来保存所用的时间，fresh用来保存新鲜橘子的个数
time, fresh = 0, 0
rows, cols = len(grid), len(grid[0])
for r in range(rows):
for c in range(cols):
# 统计新鲜橘子的数量
if grid[r][c] == 1:
fresh += 1
# 把腐烂的橘子的坐标放到队列中
if grid[r][c] == 2:
q.append((r, c))
# 腐烂橘子扩散的四个方向
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while q and fresh > 0:
q_len = len(q)
for _ in range(q_len):
cur = q.popleft()
for dr, dc in dirs:
row, col = cur[0] + dr, cur[1] + dc
if row < 0 or row >= rows or col < 0 or col >= cols or grid[row][col] != 1:
continue
grid[row][col] = 2
q.append((row, col))
fresh -= 1
# 紧邻腐烂橘子的一层新鲜橘子变腐烂，更新使用的时间
time += 1
# 最后还有新鲜的橘子返回-1
return -1 if fresh else time
复杂度分析
时间复杂度： 整个过程需要遍历网格中所有的元素，所以时间复杂度为O(mn)，其中m为网格的行数，n为网格的列数。
空间复杂度： 这里会用到一个队列，对列中的元素个数最多为mn个，所以空间复杂度为O(mn)，其中m为网格的行数，n为网格的列数。
号外
经常使用leetcode会员的同学可以使用我的优惠通道啦！
https://leetcode.cn/premium/?promoChannel=ldtiger ，年度会员有效期比官网多俩月，季度会员有效期比官网多两个星期，还有专属福利，需要的读者朋友可以找我了解。
今天的分享就到这里，希望大家能有所收获！
