【算法刷题】—7.17多源广度优先算法应用

简介: ✨今日算法一题腐烂的橘子

文章目录


腐烂的橘子


题目描述

思路详解


观察到对于所有的腐烂橘子,其实它们在广度优先搜索上是等价于同一层的节点的。

假设这些腐烂橘子刚开始是新鲜的,而有一个腐烂橘子(我们令其为超级源点)会在下一秒把这些橘子都变腐烂,而这个腐烂橘子刚开始在的时间是 −1 ,那么按照广度优先搜索的算法,下一分钟也就是第 0 分钟的时候,这个腐烂橘子会把它们都变成腐烂橘子,然后继续向外拓展,所以其实这些腐烂橘子是同一层的节点。那么在广度优先搜索的时候,我们将这些腐烂橘子都放进队列里进行广度优先搜索即可,最后每个新鲜橘子被腐烂的最短时间dis[x][y] 其实是以这个超级源点的腐烂橘子为起点的广度优先搜索得到的结果。

为了确认是否所有新鲜橘子都被腐烂,可以记录一个变量 cnt 表示当前网格中的新鲜橘子数,广度优先搜索的时候如果有新鲜橘子被腐烂,则 cnt-=1 ,最后搜索结束时如果 cnt 大于 0 ,说明有新鲜橘子没被腐烂,返回 −1 ,否则返回所有新鲜橘子被腐烂的时间的最大值即可,也可以在广度优先搜索的过程中把已腐烂的新鲜橘子的值由 1 改为 2,最后看网格中是否由值为 1 即新鲜的橘子即可。


代码与结果

class Solution {
    int[] dr = new int[]{-1, 0, 1, 0};
    int[] dc = new int[]{0, -1, 0, 1};
    public int orangesRotting(int[][] grid) {
        int R = grid.length, C = grid[0].length;
        Queue<Integer> queue = new ArrayDeque<Integer>();
        Map<Integer, Integer> depth = new HashMap<Integer, Integer>();
        for (int r = 0; r < R; ++r) {
            for (int c = 0; c < C; ++c) {
                if (grid[r][c] == 2) {
                    int code = r * C + c;
                    queue.add(code);
                    depth.put(code, 0);
                }
            }
        }
        int ans = 0;
        while (!queue.isEmpty()) {
            int code = queue.remove();
            int r = code / C, c = code % C;
            for (int k = 0; k < 4; ++k) {
                int nr = r + dr[k];
                int nc = c + dc[k];
                if (0 <= nr && nr < R && 0 <= nc && nc < C && grid[nr][nc] == 1) {
                    grid[nr][nc] = 2;
                    int ncode = nr * C + nc;
                    queue.add(ncode);
                    depth.put(ncode, depth.get(code) + 1);
                    ans = depth.get(ncode);
                }
            }
        }
        for (int[] row: grid) {
            for (int v: row) {
                if (v == 1) {
                    return -1;
                }
            }
        }
        return ans;
    }
}


✨总结


今天有些事情发生,所以算法今天只刷了一题。参考了官方解答,小伙伴们一起练一练吧。


相关文章
|
2月前
|
存储 算法 Java
解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用
在Java中,Set接口以其独特的“无重复”特性脱颖而出。本文通过解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用。
50 3
|
2月前
|
机器学习/深度学习 人工智能 自然语言处理
深度学习中的优化算法及其应用
【10月更文挑战第8天】 本文将探讨深度学习中常用的优化算法,包括梯度下降法、Adam和RMSProp等,介绍这些算法的基本原理与应用场景。通过实例分析,帮助读者更好地理解和应用这些优化算法,提高深度学习模型的训练效率与性能。
169 63
|
1月前
|
机器学习/深度学习 JSON 算法
二叉树遍历算法的应用场景有哪些?
【10月更文挑战第29天】二叉树遍历算法作为一种基础而重要的算法,在许多领域都有着不可或缺的应用,它为解决各种复杂的问题提供了有效的手段和思路。随着计算机科学的不断发展,二叉树遍历算法也在不断地被优化和扩展,以适应新的应用场景和需求。
32 0
|
2月前
|
存储 算法 搜索推荐
这些算法在实际应用中有哪些具体案例呢
【10月更文挑战第19天】这些算法在实际应用中有哪些具体案例呢
44 1
|
2月前
|
机器学习/深度学习 人工智能 算法
[大语言模型-算法优化] 微调技术-LoRA算法原理及优化应用详解
[大语言模型-算法优化] 微调技术-LoRA算法原理及优化应用详解
92 0
[大语言模型-算法优化] 微调技术-LoRA算法原理及优化应用详解
|
2月前
|
算法 安全 物联网
如何应用SM2算法进行身份认证
【10月更文挑战第5天】如何应用SM2算法进行身份认证
100 1
|
2月前
|
存储 算法 安全
SM2算法的应用场景有哪些?
【10月更文挑战第5天】SM2算法的应用场景有哪些?
128 1
|
2月前
|
监控 算法 数据挖掘
HyperLogLog算法有哪些应用场景呢
【10月更文挑战第19天】HyperLogLog算法有哪些应用场景呢
19 0
|
2月前
|
机器学习/深度学习 算法 数据建模
计算机前沿技术-人工智能算法-生成对抗网络-算法原理及应用实践
计算机前沿技术-人工智能算法-生成对抗网络-算法原理及应用实践
33 0
|
2月前
|
数据可视化 搜索推荐 Python
Leecode 刷题笔记之可视化六大排序算法:冒泡、快速、归并、插入、选择、桶排序
这篇文章是关于LeetCode刷题笔记,主要介绍了六大排序算法(冒泡、快速、归并、插入、选择、桶排序)的Python实现及其可视化过程。
17 0