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

华为OD技术面试-最短距离矩阵(动态规划、广度优先)

背景

记录2023-10-21 晚华为OD三面的手撕代码题,当时没做出来,给面试官说了我的想法,评价:解法复杂了,只是简单的动态规范 或 广度优先算法,事后找资料记录实现方式。

题目

腐烂的橘子
问题描述:
在给定的网格中,每个单元格可以有以下三个值之一:
值 0 代表空单元格;
值 1 代表新鲜橘子;
值 2 代表腐烂的橘子。
【每分钟,任何与腐烂的橘子(在 4 个正方向上)相邻的新鲜橘子都会腐烂。】
返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。【如果不可能,返回 -1。】
示例 1:
输入:[[2,1,1],[1,1,0],[0,1,1]]
输出:4
示例 2:
输入:[[2,1,1],[0,1,1],[1 ,0,1]]
输出:-1
解释:左下角的橘子(第 2 行, 第 0 列)永远不会腐烂,因为腐烂只会发生在 4 个正向上。
示例 3:
输入:[[0,2]]
输出:0
解释:因为 0 分钟时已经没有新鲜橘子了,所以答案就是 0 。

实现一(广度优先)

求解思路

就按照题目描述,
(1)按照时间 线
(2)逐步 遍历所有的位置
(3)根据规则,如果有坏橘子,且四个正方向(东南西北)有好橘子,则更新之
(4)设计一个状态变量,记录当前时刻:是否有橘子腐败,如果无橘子腐败,是 全部好,还是全部坏,亦或者 好坏相间。

代码实现

testA = [[2,1,1],[1,1,0],[0,1,1]]
testB = [[2,1,1],[0,1,1],[1,0,1]]
testC = [[0,2]]M_position = testA
print(M_position)row = len(M_position)
col = len(M_position[0])
set_bad = []for ir in range(row):for jc in range(col):if M_position[ir][jc]==1:set_bad.append((ir, jc))
print(row, col)# 一次时间变更
def onetimeupndate():# 状态变量 # 0 无橘子# 1、全部新鲜# (1, 2) 好坏 混杂,且未 感染# 2、全部坏、# 3、坏感染flag = 0# 变更状态的坐标changed_set = []for ir in range(row):for jc in range(col):if M_position[ir][jc]==0:continue# 记录唯一状态if flag!=3:flag = (flag + M_position[ir][jc])/(1 if flag==0 else 2)# 坏橘子才更新if M_position[ir][jc]!=2 or ((ir, jc) in changed_set):continue# 遍历方向for i,j in [[1,0],[0,1],[-1,0],[0,-1]]:ar_, bc_ = ir + i, jc + jif ar_<0 or ar_>=row or bc_<0 or bc_>=col:continueif M_position[ar_][bc_]==1:# 记录更新的坐标changed_set.append((ar_, bc_))# 标记状态flag = 3# 换橘子M_position[ar_][bc_]=2return flagitime = 0
while True:flag = onetimeupndate()print("当前次数",itime)print("状态变量",flag)print("最新结果",M_position)if flag!=3:if 1<flag<2:itime = -1breakitime +=1print("结果",itime)

实现二(动态规范)

求解思路

  1. 问题抽象为 求每个点 到最近的 坏的橘子的 最短距离
  2. 构造初始距离矩阵,约定:

0、坏橘子 inf、永远不坏 row*col、好橘子最大距离

  1. 做两次 扫描,更新最短距离
  2. 得到整体最短距离,找到 永不更新的点

代码实现

def calmintime(M_position):# 最短路径矩阵M_status = []# 尺寸信息row = len(M_position)col = len(M_position[0])MAXTIME = row * col# 初始矩阵for ir in range(row):for ic in range(col):if ic == 0:M_status.append([])if M_position[ir][ic] == 2: # 腐烂v = 0elif M_position[ir][ic] == 0: # 无v = infelif M_position[ir][ic] == 1: # 新鲜v = MAXTIME # 设为一个到不了的实数最大值M_status[ir].append(v)# 往左下遍历,比较右上两个方向for ir in range(row):for ic in range(col):if M_position[ir][ic]==0:continueif ic-1>=0:if M_status[ir][ic-1]+1<M_status[ir][ic]:M_status[ir][ic] = M_status[ir][ic-1]+1if ir-1>=0:if M_status[ir-1][ic]+1<M_status[ir][ic]:M_status[ir][ic] = M_status[ir-1][ic]+1# 往 右上遍历,比较左下两个方向for ir in reversed(range(row)):for ic in reversed(range(col)):if M_position[ir][ic]==0:continueif ic+1<col:if M_status[ir][ic+1]+1<M_status[ir][ic]:M_status[ir][ic] = M_status[ir][ic+1]+1if ir+1<row:if M_status[ir+1][ic]+1<M_status[ir][ic]:M_status[ir][ic] = M_status[ir+1][ic]+1# 最短距离vlist = []for ir in range(row):for ic in range(col):v = M_status[ir][ic]if not v is inf:vlist.append(v)if len(vlist)==0:return 0vmax = max(vlist)if vmax==MAXTIME: # 还存在新鲜的橘子return -1else:return vmaxtestA = [[2,1,1],[1,1,0],[0,1,1]]
testB = [[2,1,1],[0,1,1],[1,0,1]]
testC = [[0,2]]

结果验证

在这里插入图片描述

参考资料

矩阵(广度优先搜索)(动态规划)

相关文章:

华为OD技术面试-最短距离矩阵(动态规划、广度优先)

背景 记录2023-10-21 晚华为OD三面的手撕代码题&#xff0c;当时没做出来&#xff0c;给面试官说了我的想法&#xff0c;评价&#xff1a;解法复杂了&#xff0c;只是简单的动态规范 或 广度优先算法&#xff0c;事后找资料记录实现方式。 题目 腐烂的橘子 问题描述&#xff…...

【代码规范】switch 块级的作用域问题

代码规范的一些事儿 问题 今日 Git 提交代码时&#xff0c;出现报错&#xff1a; error Unexpected lexical declaration in case block no-case-declarations 解决过程 我马上就去百度&#xff0c;就找到了这篇文章&#xff1a;解决 Unexpected lexical declaration in ca…...

PHP 基础/练习

练习 成绩定级 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>成绩定级脚本</title> </…...

TCP协议与UDP协议

UDP协议 UDP协议端的格式 16位UDP长度,表示整个数据报(UDP首部UDP数据)的最大长度;如果校验和出错,就会直接丢弃; UDP的特点 UDP传输过程类似寄信 无连接 知道对端的IP和端口号就直接进行传输&#xff0c;不需要建立连接&#xff1b; 不可靠 没有任何安全机制&#xff0c…...

极智嘉(Geek+)柔性货箱到人拣选方案,助力Starlinks实现高效运营

近些年&#xff0c;电商业务席卷全球&#xff0c;一众企业蓬勃发展。比如沙特阿拉伯先进的物流与供应链解决方案供应商Starlinks的电子商务的销售额从6%增长到了23%。为满足日益增长的国际电商业务需求&#xff0c;以及订单交付时效性更高的要求&#xff0c;Starlinks与全球仓储…...

Hadoop3教程(三十一):(生产调优篇)异构存储

文章目录 &#xff08;157&#xff09;异构存储概述概述异构存储的shell操作 &#xff08;158&#xff09;异构存储案例实操参考文献 &#xff08;157&#xff09;异构存储概述 概述 异构存储&#xff0c;也叫做冷热数据分离。其中&#xff0c;经常使用的数据被叫做是热数据&…...

网络协议--UDP:用户数据报协议

11.1 引言 UDP是一个简单的面向数据报的运输层协议&#xff1a;进程的每个输出操作都正好产生一个UDP数据报&#xff0c;并组装成一份待发送的IP数据报。这与面向流字符的协议不同&#xff0c;如TCP&#xff0c;应用程序产生的全体数据与真正发送的单个IP数据报可能没有什么联…...

vscode摸鱼插件开发

不知道大家在写代码的时候&#xff0c;摸不摸鱼&#xff0c;是不是时不时得打开一下微博&#xff0c;看看今天发生了什么大事&#xff0c;又有谁塌房&#xff0c;而你没有及时赶上。 为此&#xff0c;我决定开发一个vscode插件&#xff0c;来查看微博热搜 插件名称&#xff1…...

音频录制和处理软件 Audio Hijack mac中文版说明

Audio Hijack mac是一款功能强大的音频录制和处理软件&#xff0c;它可以帮助用户从各种来源捕获和处理音频。 首先&#xff0c;Audio Hijack具有灵活的音频捕获功能。它支持从多个来源录制音频&#xff0c;包括麦克风、应用程序、网络流媒体、硬件设备等等。你可以选择捕获整个…...

寻找二叉树一个节点的后继节点

后继节点&#xff1a;中序遍历的后一个节点 普通二叉树&#xff1a;中序遍历得到一个list&#xff0c;时间复杂度O(n) 本题的二叉树&#xff1a;有父节点的指针&#xff0c;后继节点与原节点的距离为1&#xff0c;因此可以直接通过父节点找到下一个节点 优化&#xff1a;节点…...

如何能够获取到本行业的能力架构图去了解自己的能力缺陷与短板,从而能清晰的去弥补差距?

如何能够获取到本行业的能力架构图去了解自己的能力缺陷与短板&#xff0c;从而能清晰的去弥补差距&#xff1f; 获取并利用能力架构图&#xff08;Competency Model&#xff09;来了解自己在特定行业或职位中的能力缺陷和短板&#xff0c;并据此弥补差距&#xff0c;是一个非常…...

红队打靶:Misdirection打靶思路详解(vulnhub)

目录 写在开头 第一步&#xff1a;主机发现与端口扫描 第二步&#xff1a;Web渗透&#xff08;80端口&#xff0c;战术放弃&#xff09; 第三步&#xff1a;Web渗透&#xff08;8080端口&#xff09; 第四步&#xff1a;sudo bash提权 第五步&#xff1a;/etc/passwd利…...

10.23归并排序

课上 归并排序 最大时&#xff0c;就是两个都是完全倒序&#xff0c;但注意一定有一个序列先用完&#xff0c;此时剩一个序列只有一个元素&#xff0c;不用比较&#xff0c;直接加入&#xff0c;所以就是nn-1, 最小时&#xff0c;是都是完全有序&#xff0c;且一个序列中的元…...

[C++]:2初识C++(auto) + 类和对象上:

[TOC](初识C(auto) 类和对象上) 一.初始C 1.auto关键字&#xff1a;(C11) 1.作为一个变量的类型给这个类型初始化&#xff0c;auto自动识别初始化这个变量值的类型&#xff0c;为auto类型的这个变量开辟一个合适的空间。 补充&#xff1a; 1.typeid(变量名).name—>可以打…...

大学英语试卷

大学英语试卷 If everyone learns to set forth facts and reason things out in social life, many of the contradictions are easy to ____. A. oblige B. engage C. resolve D. commitIf we let the fastest runner set the____, the others will fall behind. A. pace B.…...

SpringBoot Lombok的使用

目录 下载Lombok插件 Lombok的用法 获取日志对象 生成get,set方法 Lombok框架的实现原理 Lombok的常用注解 下载Lombok插件 要使用Lombok首先要确保idea安装了lombok插件 在项目中添加 lombok依赖 在<dependency>里右键生成点击edit starters 插件(没有就下载,可…...

后台管理系统SQL注入漏洞

对于edu来说&#xff0c;是新人挖洞较好的平台&#xff0c;本次记录一次走运的捡漏0x01 前景 在进行fofa盲打站点的时候&#xff0c;来到了一个后台管理处看到集市二字&#xff0c;应该是edu站点 确认目标身份&#xff08;使用的quake进行然后去ipc备案查询&#xff09; 网…...

变量常用函数

查看变量类型 type(变量名) 用来查询变量所指的对象类型 >>> a, b, c, d 20, 5.5, True, 43j >>> print(type(a), type(b), type(c), type(d)) <class int> <class float> <class bool> <class complex> 基础数据类型 # coding…...

从零学算法(LCR 157)

某店铺将用于组成套餐的商品记作字符串 goods&#xff0c;其中 goods[i] 表示对应商品。请返回该套餐内所含商品的 全部排列方式 。 返回结果 无顺序要求&#xff0c;但不能含有重复的元素。 示例 1: 输入&#xff1a;goods “agew” 输出&#xff1a;[“aegw”,“aewg”,“ag…...

mysql 优化 聚簇索引=主键索引吗

在 InnoDB 引擎中&#xff0c;每张表都会有一个特殊的索引“聚簇索引”&#xff0c;也被称之为聚集索引&#xff0c;它是用来存储行数据的。一般情况下&#xff0c;聚簇索引等同于主键索引&#xff0c;但这里有一个前提条件&#xff0c;那就是这张表需要有主键&#xff0c;只有…...

华为云AI开发平台ModelArts

华为云ModelArts&#xff1a;重塑AI开发流程的“智能引擎”与“创新加速器”&#xff01; 在人工智能浪潮席卷全球的2025年&#xff0c;企业拥抱AI的意愿空前高涨&#xff0c;但技术门槛高、流程复杂、资源投入巨大的现实&#xff0c;却让许多创新构想止步于实验室。数据科学家…...

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

HBuilderX安装(uni-app和小程序开发)

下载HBuilderX 访问官方网站&#xff1a;https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本&#xff1a; Windows版&#xff08;推荐下载标准版&#xff09; Windows系统安装步骤 运行安装程序&#xff1a; 双击下载的.exe安装文件 如果出现安全提示&…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)

宇树机器人多姿态起立控制强化学习框架论文解析 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架&#xff08;一&#xff09; 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

Rapidio门铃消息FIFO溢出机制

关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系&#xff0c;以下是深入解析&#xff1a; 门铃FIFO溢出的本质 在RapidIO系统中&#xff0c;门铃消息FIFO是硬件控制器内部的缓冲区&#xff0c;用于临时存储接收到的门铃消息&#xff08;Doorbell Message&#xff09;。…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

MySQL 8.0 事务全面讲解

以下是一个结合两次回答的 MySQL 8.0 事务全面讲解&#xff0c;涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容&#xff0c;并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念&#xff08;ACID&#xff09; 事务是…...