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

【LeetCode】每日一题 2024_5_13 腐烂的橘子(经典多源 BFS)

文章目录

  • LeetCode?启动!!!
  • 题目:找出不同元素数目差数组
    • 题目描述
    • 代码与解题思路
  • 每天进步一点点

LeetCode?启动!!!


好久没写每日一题题解了,今天重新起航

干一件事情,永远不会太迟,只要现在开始,做什么都不算晚

题目:找出不同元素数目差数组

题目链接:994. 腐烂的橘子

题目描述

代码与解题思路

思路如标题,这道题是一道经典的多源 BFS 题目

func orangesRotting(grid [][]int) int {var dx = []int{0, 1, -1, 0}var dy = []int{1, 0, 0, -1}n, m := len(grid), len(grid[0])q := [][]int{}// 把第一轮需要 bfs 的节点找出for i := range grid {for j, v := range grid[i] {if v == 2 {q = append(q, []int{i, j})}}}ans := 0for len(q) > 0 {// 进行一轮 bfsfor sz := len(q); sz > 0; sz-- {t := q[0]q = q[1:]for i := 0; i < 4; i++ {x, y := dx[i]+t[0], dy[i]+t[1]if x < 0 || x >= n || y < 0 || y >= m || grid[x][y] != 1 {continue}grid[x][y] = 2q = append(q, []int{x, y})}}if len(q) > 0 {ans++}}// 如果还有新鲜的橘子, 则返回 -1for i := range grid {for _, v := range grid[i] {if v == 1 {return -1}}}return ans
} 

这是经典的多源 bfs 解题模板,我的解法,不过,最后再遍历一次判断是否还有新鲜橘子的操作可能略有些丑陋

可以看看灵神的判断方式,通过 fresh 变量的计数判断:

type pair struct{ x, y int }
var directions = []pair{{-1, 0}, {1, 0}, {0, -1}, {0, 1}} // 四方向func orangesRotting(grid [][]int) int {m, n := len(grid), len(grid[0])fresh := 0q := []pair{}for i, row := range grid {for j, x := range row {if x == 1 {fresh++ // 统计新鲜橘子个数} else if x == 2 {q = append(q, pair{i, j}) // 一开始就腐烂的橘子}}}ans := -1for len(q) > 0 {ans++ // 经过一分钟tmp := qq = []pair{}for _, p := range tmp { // 已经腐烂的橘子for _, d := range directions { // 四方向i, j := p.x+d.x, p.y+d.yif 0 <= i && i < m && 0 <= j && j < n && grid[i][j] == 1 { // 新鲜橘子fresh--grid[i][j] = 2 // 变成腐烂橘子q = append(q, pair{i, j})}}}}if fresh > 0 {return -1}return max(ans, 0)
}

每天进步一点点

可以和我刷一辈子的每日一题吗?
一题一题,积累起来就是一辈子。

相关文章:

【LeetCode】每日一题 2024_5_13 腐烂的橘子(经典多源 BFS)

文章目录 LeetCode&#xff1f;启动&#xff01;&#xff01;&#xff01;题目&#xff1a;找出不同元素数目差数组题目描述代码与解题思路 每天进步一点点 LeetCode&#xff1f;启动&#xff01;&#xff01;&#xff01; 好久没写每日一题题解了&#xff0c;今天重新起航 干…...

【Linux系统编程】第十七弹---进程理解

✨个人主页&#xff1a; 熬夜学编程的小林 &#x1f497;系列专栏&#xff1a; 【C语言详解】 【数据结构详解】【C详解】【Linux系统编程】 目录 1、进程的基本概念 2、描述进程-PCB 2.1、什么是PCB 2.2、为什么要有PCB 3、task_ struct 3.1、启动进程 3.2、创建进程…...

【网络安全入门】你必须要有的学习工具(附安装包)零基础入门到进阶,看这一篇就够了!

工欲善其事必先利其器 在新入门网络安全的小伙伴而言。这些工具你必须要有所了解。本文我们简单说说这些网络安全工具吧&#xff01; Web安全类 Web类工具主要是通过各种扫描工具&#xff0c;发现web站点存在的各种漏洞如sql注入、xss等。从而获取系统权限&#xff0c;常用的…...

【解决】:git clone项目报错fatal: fetch-pack: invalid index-pack output

象&#xff1a;之前一直使用gitee将个人学习和工作相关记录上传到个人gitee仓库&#xff0c;一直没出现过问题。直到有一天换电脑重新拉取代码发现出了问题&#xff0c;具体如下图&#xff1a; 原因分析&#xff1a; 经过查询发现主要原因是因为git clone的远程仓库的项目过大…...

python随机显示四级词汇

python实现一个浮动窗口随机显示四级单词在桌面跑来跑去 实现一个浮动窗体随机显示四级单词在windows桌面置顶移动 tkinter库来创建窗口和显示单词&#xff0c;以及random库来随机选择单词。 使用after方法来定时更新窗口的位置&#xff0c;实现单词窗口的慢慢移动效果 使用…...

vuerouter声明式导航

声明式导航-跳转传参数 1.查询参数传参 语法&#xff1a;to /path?参数名值 2.对应页面组件接受传来的值 $router.query.参数名 2.动态路由传参 1.配置动态路由 2.配置导航连接 to/path/参数值 3.对应页面组件接收传递过来的值 #route.params.参数名 多个参数传递&…...

视频断点上传

什么是断点续传 通常视频文件都比较大&#xff0c;所以对于媒资系统上传文件的需求要满足大文件的上传要求。http协议本身对上传文件大小没有限制&#xff0c;但是客户的网络环境质量、电脑硬件环境等参差不齐&#xff0c;如果一个大文件快上传完了网断了没有上传完成&#xf…...

清华团队开发首个AI医院小镇模拟系统;阿里云发布通义千问 2.5:超越GPT-4能力;Mistral AI估值飙升至60亿美元

&#x1f989; AI新闻 &#x1f680; 清华团队开发首个AI医院小镇模拟系统 摘要&#xff1a;来自清华的研究团队最近开发出了一种创新的模拟系统&#xff0c;名为"Agent Hospital"&#xff0c;该系统能够完全模拟医患看病的全流程&#xff0c;其中包括分诊、挂号、…...

React Suspense与Concurrent Mode:探索异步渲染的新范式

React的Suspense和Concurrent Mode是两个强大的特性&#xff0c;它们共同改变了React应用处理异步数据加载和UI渲染的方式。下面我将通过一个简化的代码示例来展示如何使用这两个特性。 Concurrent Mode 和 Suspense 的基本用法 首先&#xff0c;确保你使用的是支持这些特性的…...

算法训练营day37

动态规划 1.斐波那契数 1.使用数组存储子问题结果 class Solution {public int fib(int N) {if (N 0) return 0;int[] dp new int[N 1];// base casedp[0] 0; dp[1] 1;// 状态转移for (int i 2; i < N; i) {dp[i] dp[i - 1] dp[i - 2];}return dp[N];} }2.使用变…...

基础ArkTS组件:帧动画,内置动画组件,跑马灯组件(HarmonyOS学习第三课【3.6】)

帧动画 帧动画也叫序列帧动画&#xff0c;其原理就是在时间轴的每帧上逐帧绘制不同的内容&#xff0c;使其连续播放而成动画。ArkUI开发框架提供了 ImageAnimator 组件实现帧动画能力&#xff0c;本节笔者介绍一下 ImageAnimator 组件的简单使用。 官方文献 说明 该组件从A…...

vant NavBar 导航栏详解

vant 是一个基于 Vue 的移动端 UI 组件库&#xff0c;而 NavBar 是其中的一个导航栏组件。下面是对 vant 的 NavBar 导航栏组件的详细解释&#xff1a; 1. 引入 NavBar 首先&#xff0c;你需要在你的 Vue 组件中引入 NavBar 组件&#xff1a; import { NavBar } from vant; …...

Python自动化办公实战案例:文件整理与邮件发送

目录 一、引言 二、案例背景 三、实战案例 &#xff08;一&#xff09;文件自动整理 &#xff08;二&#xff09;邮件自动发送 四、结语 一、引言 随着办公自动化的兴起&#xff0c;Python作为一门强大的编程语言&#xff0c;逐渐被应用于日常办公中。从文件整理到邮件…...

2024中国(重庆)无人机展览会8月在重庆举办

2024中国(重庆)无人机展览会8月在重庆举办 邀请函 主办单位&#xff1a; 中国航空学会 重庆市南岸区人民政府 招商执行单位&#xff1a; 重庆港华展览有限公司 报名&#xff1a;【交易会I 59交易会2351交易会9466】 展会背景&#xff1a; 为更好的培养航空航天产业和无人…...

自动驾驶技术与传感器数据处理

目录 自动驾驶总体架构 感知系统 决策系统 定位系统 ​计算平台​ 仿真平台​ 自动驾驶公开数据集 激光点云 点云表征方式 1) 原始点云 2) 三维点云体素化 3)深度图 4)鸟瞰图 点云检测障碍物的步骤 PCL点云库 车载毫米波雷达 车载相机 设备标定 自动驾驶…...

高效测评系统方案助力沃尔玛、亚马逊卖家提升产品销量

无论在哪个电商平台&#xff0c;测评确实是最有效的推广方式。测之前一定要选好产品&#xff0c;因为对于大部分卖家而言&#xff0c;不可能你店铺里所有的都是爆款&#xff0c;所以选择的是需要有潜力成为爆款的产品。测评是指通过搭建安全的环境模拟真实的买家购物行为&#…...

B/S模式的web通信(高并发服务器)

这里写目录标题 目标实现的目标 服务器代码&#xff08;采用epoll实现服务器&#xff09;整体框架main函数init_listen_fd函数&#xff08;负责对lfd初始化的那一系列操作&#xff09;epoll_run函数do_accept函数do_read函数内容补充&#xff1a;http中的getline函数 详解do_re…...

C语言每日一题—约瑟夫问题

13个人围成一圈&#xff0c;从第1个人开始顺序报号1、2、3&#xff0c;凡报到3的人退出圈子。找出最后留在圈子里的人原来的序号。要求用结构体编程实现。***输出提示&#xff1a;"\n出圈成员及顺序&#xff1a;" ***输出格式&#xff1a;"%3d" ***输出提示…...

语言:C#

一、VSCode生成exe 二、...

[力扣题解]45. 跳跃游戏 II

题目&#xff1a;45. 跳跃游戏 II 思路 贪心法&#xff1b; 只需记录2个变量&#xff0c;当前点能达到的最远距离&#xff0c;和上一步能到达的最远距离&#xff1b; &#xff08;真有意思&#xff0c;代码随想录给出的是curDistance&#xff0c;nextDistance2个&#xff0c;…...

web vue 项目 Docker化部署

Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段&#xff1a; 构建阶段&#xff08;Build Stage&#xff09;&#xff1a…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

IT供电系统绝缘监测及故障定位解决方案

随着新能源的快速发展&#xff0c;光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域&#xff0c;IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选&#xff0c;但在长期运行中&#xff0c;例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...