【华为机试真题详解 Python实现】静态扫描最优成本【2023 Q1 | 100分】
文章目录
- 前言
- 题目描述
- 输入描述
- 输出描述
- 示例 1
- 输入:
- 输出:
- 示例 2
- 输入:
- 输出:
- 题目解析
- 参考代码
前言
《华为机试真题详解》专栏含牛客网华为专栏、华为面经试题、华为OD机试真题。
如果您在准备华为的面试,期间有想了解的可以私信我,我会尽可能帮您解答,也可以给您一些建议!
本文解法非最优解(即非性能最优),不能保证通过率。
特别提醒!!!!
注意1:机试为ACM 模式
你的代码需要处理输入输出,input接收输入、注意2:机试按通过率记分
复杂题目可以考虑暴力破解,再逐步优化,不是运行超时就无法得分,如下,提交结果运行超时,但用例通过率>92.31% , 如果是100分的题目,可以得92.3分。
题目描述
静态扫描快速识别源代码的缺陷,静态扫描的结果以扫描报告作为输出:
- 文件扫描的成本和文件大小相关,如果文件大小为 ,则扫描成本为
N个金币 - 扫描报告的缓存成本和文件大小无关,每缓存一个报告需要
M个金币 - 扫描报告缓存后,后继再碰到该文件则不需要扫描成本,直接获取缓存结果
给出源代码文件标识序列和文件大小序列,求解采用合理的缓存策略,最少需要的 金币Q数
输入描述
第一行为缓存一个报告金币数 M,1 <= M <=100
第二行为文件标识序列: F1,F2,F3…Fn,其中1 <= N <= 10000,1 <= F <=1000
第三行为文件大小序列: S1,S2,S3…Sn,其中1 <= N <= 10000,1 <= S <=10
输出描述
采用合理的缓存策略,需要的最少金币数
示例 1
输入:
5
1 2 2 1 2 3 4
1 1 1 1 1 1 1
输出:
7
说明:
文件大小相同,扫描成本均为1个金币。缓存任意文件均不合算,所以每次都是重新扫描文本,因而最少成本为7金币
示例 2
输入:
5
2 2 2 2 2 5 2 2 2
3 3 3 3 3 1 3 3 3
输出:
9
说明:
2号文件出现了8次,不缓存成本为 3*8=24,扫描加缓存成本共计 3+5=8,显然缓存更优,最优成本为 8+1=9
题目解析
获取文件的方式有两种:
第一种是扫描文件,成本包含扫描文件成本;
第二种是从缓存中读取文件,成本包含一次扫描文件成本 + 缓存文件的成本。
我们只需要获取到每个文本的扫描次数与缓存方案的成本进行比较,单个文件选择最优方案,整体成本即为最优方案(贪婪)。
这个方式再业务中也有很多应用场景,例如:
数据访问优化,对于数据库热点数据的访问,首先从数据库获取数据,生成键值并存储在缓存中,下次再获取该数据时直接从缓存中加载,减少数据获取的延时。
在业务场景中高速缓存的使用成本较高,我们可能需要考虑过期时间、淘汰策略等问题,而这道题目中没有缓存加载顺序,使用限制等说明,所以这道题目中不需要考虑。

参考代码
while 1:try:m = int(input())fList = list(map(int, input().split()))sList = list(map(int, input().split()))cache = []total = 0for i in range(len(fList)):if fList[i] in cache:continuecache.append(fList[i])c = fList.count(fList[i])total += min(sList[i] * c, sList[i] + m)print(total)except Exception as e:break
或者保存分项
while 1:try:m = int(input())fList = list(map(int, input().split()))sList = list(map(int, input().split()))cache = {}for i in range(len(fList)):if fList[i] in cache:continuec = fList.count(fList[i])cache[fList[i]] = min(sList[i] * c, sList[i] + m)print(sum(cache.values()))except Exception as e:import tracebackprint(traceback.print_exc())break
最后,如果你有什么样的问题或解题心得,欢迎评论区交流!
相关文章:
【华为机试真题详解 Python实现】静态扫描最优成本【2023 Q1 | 100分】
文章目录前言题目描述输入描述输出描述示例 1输入:输出:示例 2输入:输出:题目解析参考代码前言 《华为机试真题详解》专栏含牛客网华为专栏、华为面经试题、华为OD机试真题。 如果您在准备华为的面试,期间有想了解的…...
算法刷题总结 (四) 动态规划
算法总结4 动态规划一、动态规划1.1、基础问题11.1.1、509. 斐波那契数列1.1.2、70. 爬楼梯1.1.3、746. 使用最小花费爬楼梯1.2、基础问题21.2.1、62. 不同路径1.2.2、63. 不同路径Ⅱ1.2.3、343. 整数拆分1.2.4、96. 不同的二叉搜索树1.3、背包问题1.3.1、01背包1.3.1.1、单次选…...
Grafana 转换数据的工具介绍
转换数据 Grafana 可以在数据显示到面板前对数据进行处理 1、点击Transform选项卡 2、选择要使用的转换类型,不同的转换类型配置不同 3、要新增转换类型,点击Add transformation 4、使用右上角调式按钮可以调式转换 支持的转换类型: Add f…...
Linux 学习笔记
一、 概述 1. 操作系统 ① 计算机由硬件和软件组成 ② 操作系统属于软件范畴,主要作用是协助用户调度硬件工作,充当用户和计算机硬件之间的桥梁 ③ 常见的操作系统 🤠 PC端:Windows、Linux、MacOS🤠 移动端&#…...
HTML注入专精整理
目录 HTML注入介绍 抽象解释 HTML注入的影响 HTML注入与XSS的区别 HTML元素流程图...
看完这篇我不信你不会二叉树的层序遍历【C语言】
目录 实现思路 代码实现 之前介绍了二叉树的前、中、后序三种遍历,采用的是递归的方式。今天我们来学习另外一种遍历方式——层序遍历。层序遍历不容小觑,虽然实现方法并不难,但是它所采取的思路是很值得学习的,与前三者不同&am…...
案例17-环境混用带来的影响
目录一、背景介绍背景事故二、思路&方案三、过程四、总结nginx做转发fastdfs(文件上传下载)五、升华一、背景介绍 本篇博客主要介绍开发中项目使用依赖项环境闭一只带来的恶劣影响,在错误中成长进步。 背景 本公司另外一个产品开发God…...
知识蒸馏论文阅读:DKD算法笔记
标题:Decoupled Knowledge Distillation 会议:CVPR2022 论文地址:https://ieeexplore.ieee.org/document/9879819/ 官方代码:https://github.com/megvii-research/mdistiller 作者单位:旷视科技、早稻田大学、清华大学…...
Sentinel架构篇 - 熔断降级
熔断降级 概念 除了流量控制以外,对调用链路中不稳定的资源进行熔断降级也是保障高可用的重要措施之一。一个服务常常会调用其它模块,可能是一个远程服务、数据库、或者第三方 API 等。然而,被依赖的服务的稳定性是不能保证的。如果依赖的服…...
shell脚本的一些记录 与jenkins的介绍
shell 脚本的执行 sh ***.sh shell脚本里面的命令 其实就是终端执行一些命令 shell 连接服务器 可以直接ssh连接 但是这样最好是无密码的 不然后面的命令就不好写了 换而言之有密码得 不好写脚本 需要下载一些expect的插件之类的才可以 判断语句 的示例 需要注意的是…...
JVM的了解与学习
一:jvm是什么 jvm是java虚拟机java Virtual Machine的缩写 jdk包含jre和java DevelopmentTools 二:什么是java虚拟机 虚拟机是一种抽象化的计算机,通过在实际的计算机上仿真模拟各种计算机功能来实现的。java虚拟机有自己完善的硬体结构,如处理器、堆栈、寄存器等,还有…...
提升数字品牌的5个技巧
“品牌”或“品牌推广”的概念通常用于营销。因为建立您的企业品牌对于产品来说极其重要,品牌代表了您与客户互动的身份和声音。今天,让我们来看看在数字领域提升品牌的一些有用的技巧。如何在数字领域提升您的品牌?在了解这些技巧之前&#…...
java通过反射获取加了某个注解的所有的类
有时候我们会碰到这样的情况:有n个场景,每个场景都有自己的逻辑,即n个处理逻辑,这时候我们就需要通过某个参数的值代表这n个场景,然后去加载每个场景不同的bean对象,即不同的类,这些类中都有一个…...
Warshall算法
🚀write in front🚀 📜所属专栏:> 算法 🛰️博客主页:睿睿的博客主页 🛰️代码仓库:🎉VS2022_C语言仓库 🎡您的点赞、关注、收藏、评论,是对我…...
vector中迭代器失效的问题及解决办法
目录 vector常用接口 vector 迭代器失效问题 vector中深浅拷贝问题 vector的数据安排以及操作方式,与array非常相似。两者的唯一差别在于空间的运用的灵活性。array 是静态空间,一旦配置了就不能改变;要换个大(或小) 一点的房子&#x…...
【蓝桥杯刷题训练营】day05
1 数的分解 拆分成3个数相加得到该数 然后采用了一种巨愚蠢的办法: int main() {int count 0;int a 2;int b 0;int c 1;int d 9;int a1, a2, a3;int c1, c2, c3;int d1, d2, d3;for (a1 0; a1 < 2; a1){for (a2 0; a2 < 2; a2){for (a3 0; a3 <…...
线程中断interrupt导致sleep产生的InterruptedException异常
强制当前正在执行的线程休眠(暂停执行),以“减慢线程”。 Thread.sleep(long millis)和Thread.sleep(long millis, int nanos)静态方法当线程睡眠时,它睡在某个地方,在苏醒之前不会返回到可运行状态。 当睡眠时间到期…...
ubuntu的快速安装与配置
文章目录前言一、快速安装二 、基础配置1 Sudo免密码2 ubuntu20.04 pip更新源3 安装和配置oneapi(infort/mpi/mkl) apt下载第一次下载的要建立apt源apt下载(infort/mpi/mkl)4 安装一些依赖库等5 卸载WSLpython总结前言 win11系统 ubuntu20.04 提示:以下…...
人工智能AI工具汇总(AIGC ChatGPT时代个体崛起)
NameCategoryWebsiteDescription描述《AIGC时代:超级个体的崛起》小报童https://xiaobot.net/p/SuperIndividual 介绍AIGC,ChatGPT,使用技巧与搞钱方式。Masterpiece Studio3Dhttps://masterpiecestudio.comSimplifying 3D Creation with AI…...
【rust-grpc-proxy】在k8s中,自动注入代理到pod中,再不必为grpc调试而烦恼
目录前言原理sidecarwebhook实现安装k8s设置webhook使用尾语前言 rust-grpc-proxy 目前功能基本完善。是时候上环境开始应用了。 之前考虑是gateway模式或者sidecar模式。 思考良久之后,觉得两种模式都有使用场景,那就都支持。本次就带来sidecar模式的食…...
多模态2025:技术路线“神仙打架”,视频生成冲上云霄
文|魏琳华 编|王一粟 一场大会,聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中,汇集了学界、创业公司和大厂等三方的热门选手,关于多模态的集中讨论达到了前所未有的热度。其中,…...
Unity3D中Gfx.WaitForPresent优化方案
前言 在Unity中,Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染(即CPU被阻塞),这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案: 对惹,这里有一个游戏开发交流小组&…...
Mysql中select查询语句的执行过程
目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析(Parser) 2.4、执行sql 1. 预处理(Preprocessor) 2. 查询优化器(Optimizer) 3. 执行器…...
Go 并发编程基础:通道(Channel)的使用
在 Go 中,Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式,用于在多个 Goroutine 之间传递数据,从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...
Rust 开发环境搭建
环境搭建 1、开发工具RustRover 或者vs code 2、Cygwin64 安装 https://cygwin.com/install.html 在工具终端执行: rustup toolchain install stable-x86_64-pc-windows-gnu rustup default stable-x86_64-pc-windows-gnu 2、Hello World fn main() { println…...
java高级——高阶函数、如何定义一个函数式接口类似stream流的filter
java高级——高阶函数、stream流 前情提要文章介绍一、函数伊始1.1 合格的函数1.2 有形的函数2. 函数对象2.1 函数对象——行为参数化2.2 函数对象——延迟执行 二、 函数编程语法1. 函数对象表现形式1.1 Lambda表达式1.2 方法引用(Math::max) 2 函数接口…...
PydanticAI快速入门示例
参考链接:https://ai.pydantic.dev/#why-use-pydanticai 示例代码 from pydantic_ai import Agent from pydantic_ai.models.openai import OpenAIModel from pydantic_ai.providers.openai import OpenAIProvider# 配置使用阿里云通义千问模型 model OpenAIMode…...
Spring事务传播机制有哪些?
导语: Spring事务传播机制是后端面试中的必考知识点,特别容易出现在“项目细节挖掘”阶段。面试官通过它来判断你是否真正理解事务控制的本质与异常传播机制。本文将从实战与源码角度出发,全面剖析Spring事务传播机制,帮助你答得有…...
VSCode 没有添加Windows右键菜单
关键字:VSCode;Windows右键菜单;注册表。 文章目录 前言一、工程环境二、配置流程1.右键文件打开2.右键文件夹打开3.右键空白处打开文件夹 三、测试总结 前言 安装 VSCode 时没有注意,实际使用的时候发现 VSCode 在 Windows 菜单栏…...
比较数据迁移后MySQL数据库和ClickHouse数据仓库中的表
设计一个MySQL数据库和Clickhouse数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...

