腐烂的橘子 -- 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博客 在工具/选项/调试…...
阿里云ACP云计算备考笔记 (5)——弹性伸缩
目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...
Qt Widget类解析与代码注释
#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码,写上注释 当然可以!这段代码是 Qt …...
华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...
从零实现STL哈希容器:unordered_map/unordered_set封装详解
本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说,直接开始吧! 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...
Rust 异步编程
Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...
BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践
6月5日,2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席,并作《智能体在安全领域的应用实践》主题演讲,分享了在智能体在安全领域的突破性实践。他指出,百度通过将安全能力…...
Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信
文章目录 Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket(服务端和客户端都要)2. 绑定本地地址和端口&#x…...
【Go语言基础【12】】指针:声明、取地址、解引用
文章目录 零、概述:指针 vs. 引用(类比其他语言)一、指针基础概念二、指针声明与初始化三、指针操作符1. &:取地址(拿到内存地址)2. *:解引用(拿到值) 四、空指针&am…...
MFC 抛体运动模拟:常见问题解决与界面美化
在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...
破解路内监管盲区:免布线低位视频桩重塑停车管理新标准
城市路内停车管理常因行道树遮挡、高位设备盲区等问题,导致车牌识别率低、逃费率高,传统模式在复杂路段束手无策。免布线低位视频桩凭借超低视角部署与智能算法,正成为破局关键。该设备安装于车位侧方0.5-0.7米高度,直接规避树枝遮…...
