腐烂的橘子 -- DFS、BFS
994. 腐烂的橘子
class OrangesRotting:"""994. 腐烂的橘子https://leetcode.cn/problems/rotting-oranges/description/"""def solution(self, grid: List[List[int]]) -> int:"""BFS时间复杂度 O(M*N)空间复杂度 O(M*N):param grid::return:"""row, col, time = len(grid), len(grid[0]), 0directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]queue = []# add the rotten orange to the queuefor i in range(row):for j in range(col):if grid[i][j] == 2:queue.append((i, j, time))# bfswhile queue:i, j, time = queue.pop(0)for di, dj in directions:if 0 <= i + di < row and 0 <= j + dj < col and grid[i + di][j + dj] == 1:grid[i + di][j + dj] = 2queue.append((i+di, j+dj, time+1))# if there are still fresh oranges, return -1for row in grid:if 1 in row:return -1return timedef solution1(self, grid: List[List[int]]) -> int:"""DFS时间复杂度 O((M*N)^2)空间复杂度 O(M*N):param grid::return:"""rows, cols = len(grid), len(grid[0])fresh = set()rotten = set()# Find positions of fresh and rotten orangesfor r in range(rows):for c in range(cols):if grid[r][c] == 1:fresh.add((r, c))elif grid[r][c] == 2:rotten.add((r, c))def dfs(r, c, minutes):# Check if position is valid and orange is freshif r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != 1:return# If the current rotting time is less than the stored value# update it and continue DFS to adjacent orangesif (r, c) in fresh and minutes < self.time_to_rot.get((r, c), float('inf')):self.time_to_rot[(r, c)] = minutesdfs(r + 1, c, minutes + 1)dfs(r - 1, c, minutes + 1)dfs(r, c + 1, minutes + 1)dfs(r, c - 1, minutes + 1)# Dictionary to store the time taken to rot each fresh orangeself.time_to_rot = {}# Start DFS from each rotten orangefor r, c in rotten:dfs(r + 1, c, 1)dfs(r - 1, c, 1)dfs(r, c + 1, 1)dfs(r, c - 1, 1)# If there are fresh oranges that never rot, return -1if len(fresh) != len(self.time_to_rot):return -1# Return the maximum time taken to rot any fresh orangereturn max(self.time_to_rot.values(), default=0)相关文章:
腐烂的橘子 -- DFS、BFS
994. 腐烂的橘子 class OrangesRotting:"""994. 腐烂的橘子https://leetcode.cn/problems/rotting-oranges/description/"""def solution(self, grid: List[List[int]]) -> int:"""BFS时间复杂度 O(M*N)空间复杂度 O(M*N):par…...
java swing UI第三方设计器JFormDesiner和FlatLaf UI
安装JFormDesiner 官网:https://www.formdev.com/ 先去IDEA的插件市场安装吧 JFormDesiner是非开源,且付费的插件,可以自己去找找不付费的使用方法。在swing可视化设计UI非常高效快捷,初学者可能需要一定时间探索,熟…...
前端JS实现全屏和退出全屏的效果
全屏效果想必我们都很清楚把,平时追剧看电视剧什么都会使用全屏方便我们看,我们键盘的第一个键esc可以退出全屏,那么我们如何用js实现全屏的办法呢? 设置全屏 Document.requestFullscreen(),该方法用于异步请求使元素…...
蓝桥杯C组-填充-贪心
点击此处查看原题 *思路:首先要求 00 11 尽可能的多,所以尽可能多的多配对,配对只在i , i 1之间发生,所以只需要关注str[i] 和 str[i 1]即可,如果str[i] str[i 1] ,那么一定配对&#x…...
mysql查询当天、近一周、近一个月及近一年的数据以及各种报表查询sql
以下是一些常见的MySQL查询语句,用于查询当天、近一周、近一个月和近一年的数据,以及一些常见的报表查询。 查询当天的数据: SELECT * FROM table_name WHERE DATE(date_column) CURDATE();查询近一周的数据: SELECT * FROM t…...
C# 使用Fleck创建WebSocket服务器
目录 写在前面 代码实现 服务端代码 客户端代码 调用示例 写在前面 Fleck 是 C# 实现的 WebSocket 服务器,通过 WebSocket API,浏览器和服务器只需要做一个握手的动作,然后浏览器和服务器之间就形成了一条快速通道;两者之间…...
Android中的SPI实现
Android中的SPI实现 SPI是JVM世界中的标准API,但在Android应用程序中并不常用。然而,它可以非常有用地实现插件架构。让我们探讨一下如何在Android中利用SPI。 问题 在Android中,不同的提供者为推送功能提供服务,而在大型项目中…...
什么是设计模式(第7章笔记)
目录 一、什么是设计模式 二、设计模式概要 1、名称 2、问题 3、解决方案 4、效果 三、《设计模式》的结构 四、小结 一、什么是设计模式 设计模式:是对已经分析过的问题,以及相关问题解决方案的优秀实践; 1、同样的问题总是重复出现&…...
【python入门】day27: 模拟高铁售票系统
界面 代码 #-*- coding:utf-8 -*- import prettytable as pt#---------导入漂亮表格 import os.path filename ticket.txt#更新座位状态 def update(row_num):#------更新购票状态with open(filename,w,encodingutf-8) as wfile:for i in range(row_num):lst1 [f{i1},有票,有…...
智能助手的巅峰对决:ChatGPT对阵文心一言
在人工智能的世界里,ChatGPT与文心一言都是备受瞩目的明星产品。它们凭借先进的技术和强大的性能,吸引了大量用户的关注。但究竟哪一个在智能回复、语言准确性、知识库丰富度等方面更胜一筹呢?下面就让我们一探究竟。 首先来谈谈智能回复能力…...
Android系统开发之浅谈广播接收器回调
广播接器BroadcastReceiver 广播Intent和广播接收器BroadcastReceiver,是大家android开发用的特别多的二个控件。 那如何从系统角度看待广播和广播接收器呢? 对于静态注册BroadcastReceiver和动态注册的BroadcastReceiver是如何回调其onReceive方法呢…...
PiflowX如何快速开发flink程序
PiflowX如何快速开发flink程序 参考资料 Flink最锋利的武器:Flink SQL入门和实战 | 附完整实现代码-腾讯云开发者社区-腾讯云 (tencent.com) Flink SQL 背景 Flink SQL 是 Flink 实时计算为简化计算模型,降低用户使用实时计算门槛而设计的一套符合标…...
Mysql运算符
文章目录 比较运算符< > !IS NULL \ IS NOT NULL \ ISNULLLEAST() \ GREATEST() 查询数据大小(字典序)BETWEEN...AND...IN (SET) \ NOT IN (SET)LIKE 模糊查询REGEXP \ RLIKE 逻辑运算符逻辑运算符: OR (||)、A…...
软件架构之事件驱动架构
一、定义 事件驱动的架构是围绕事件的发布、捕获、处理和存储(或持久化)而构建的集成模型。 某个应用或服务执行一项操作或经历另一个应用或服务可能想知道的更改时,就会发布一个事件(也就是对该操作或更改的记录)&am…...
C++ 后端面试 - 题目汇总
文章目录 🍺 非技术问题🍻 基本问题🥂 请自我介绍?🥂 你有什么问题需要问我的? 🍻 加班薪资🥂 你对加班有什么看法?🥂 你的薪资期望是多少?【待回…...
zds1104示波器使用指南
1、设置语言 2、功能检测验证示波器是否正常工作 3、示波器面板按钮详解 3.1、软键 3.2、运行控制与操作区 3.3、水平控制区 3.4、垂直控制区 3.5、多功能控制区 3.6、断电启动恢复,auto setup,default setup,恢复出厂设置详细解释 3.7、触…...
uni-app修改头像和个人信息
效果图 代码(总) <script setup lang"ts"> import { reqMember, reqMemberProfile } from /services/member/member import type { MemberResult, Gender } from /services/member/type import { onLoad } from dcloudio/uni-app impor…...
IDEA 中搭建 Spring Boot Maven 多模块项目 (父SpringBoot+子Maven)
第1步:新建一个SpringBoot 项目 作为 父工程 [Ref] 新建一个SpringBoot项目 删除无用的 .mvn 目录、 src 目录、 mvnw 及 mvnw.cmd 文件,最终只留 .gitignore 和 pom.xml 第2步:创建 子maven模块 第3步:整理 父 pom 文件 ① …...
竞赛保研 基于计算机视觉的身份证识别系统
0 前言 🔥 优质竞赛项目系列,今天要分享的是 基于机器视觉的身份证识别系统 该项目较为新颖,适合作为竞赛课题方向,学长非常推荐! 🧿 更多资料, 项目分享: https://gitee.com/dancheng-sen…...
在visual studio中调试时无法查看std::wstring
1.问题 在调试的时候发现std::wstring类型的变量查看不了,会显示(error)|0,百思不得其解。 2.解决方法 参考的:vs2015调试时无法显示QString变量的值,只显示地址_vs调试qstring的时候如何查看字符串-CSDN博客 在工具/选项/调试…...
web vue 项目 Docker化部署
Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段: 构建阶段(Build Stage):…...
使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...
基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真
目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销,平衡网络负载,延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...
从WWDC看苹果产品发展的规律
WWDC 是苹果公司一年一度面向全球开发者的盛会,其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具,对过去十年 WWDC 主题演讲内容进行了系统化分析,形成了这份…...
循环冗余码校验CRC码 算法步骤+详细实例计算
通信过程:(白话解释) 我们将原始待发送的消息称为 M M M,依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)(意思就是 G ( x ) G(x) G(x) 是已知的)࿰…...
python/java环境配置
环境变量放一起 python: 1.首先下载Python Python下载地址:Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个,然后自定义,全选 可以把前4个选上 3.环境配置 1)搜高级系统设置 2…...
DAY 47
三、通道注意力 3.1 通道注意力的定义 # 新增:通道注意力模块(SE模块) class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...
Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)
目录 1.TCP的连接管理机制(1)三次握手①握手过程②对握手过程的理解 (2)四次挥手(3)握手和挥手的触发(4)状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...
(二)原型模式
原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...
Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器
第一章 引言:语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域,文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量,支撑着搜索引擎、推荐系统、…...
