算法笔试模拟题精解之“打怪兽”-阿里云开发者社区

开发者社区> 被纵养的懒猫> 正文

算法笔试模拟题精解之“打怪兽”

简介: 根据题意,本题可使用贪心算法完成,策略是每次打怪兽都选择代价最小的一只。
+关注继续查看

在线编程介绍

阿里云开发者社区在线编程产品,针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等,界面整洁明了,操作简单,为用户营造专心答题的学习环境。点击链接开始体验:https://developer.aliyun.com/coding

本文为大家介绍其中的 第43 题:打怪兽 的题目解析,具体如下:

题目描述

题目等级:容易
知识点:排序、贪心

查看题目:打怪兽 现在有3只怪兽,他们的都有自己的血量a,b,c(1<=a,b,c<=100),当Tom打死第一怪兽的时候花费的代价为0,其余的怪兽的代价为当前的怪兽的血量减去上一个怪兽的血量的绝对值。问Tom打死这些怪兽所需要的最小代价?

分别输入三只怪兽的血量;

输出打死三只怪兽的最小代价。

示例1
输入:
2
5
8
输出:
6

解题思路:贪心

贡献者 | 郭达彬

根据题意,本题使用贪心算法完成,策略是每次打怪兽都选择代价最小的一只。

由于第一次打怪兽的花费为0,所以第一次可以打血量最小的(最大的也可以),接下来每次选择怪兽的时候就可以选择花费代价最小的。由于每次打怪兽的代价都是:当前怪兽的血量和上一个怪兽的血量的差的绝对值。于是可以得出结论,最小代价为所有怪兽血量的最大值减最小值。

时间复杂度:O(1)
空间复杂度:O(1)

趁热打铁,题目直达链接:43题:打怪兽
720-150.png

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
NOIP-C++大神培养计划 Step1.1.2基础算法——模拟算法2
大家好,我是小笨笨,今天我们继续来讲解模拟算法。 我们直接上例题! 栗1.1.2-1 洛谷P1014 Cantor表https://www.luogu.org/problemnew/show/P1014题目描述现代数学的著名证明之一是Georg Cantor证明了有理数是可枚举的。
948 0
进化算法可以不再需要计算集群,开普敦大学的新方法用一块GPU也能刷新MNIST记录
他们实验中只使用了一块GTX1070 GPU,训练时间6到24小时,就可以取得这样的成果,他们觉得非常满意。他们的研究也首次尝试了把神经进化用在一维卷积网络的创造中,用来解决情感分析、包括嵌入层的优化问题。
1297 0
怎么设置阿里云服务器安全组?阿里云安全组规则详细解说
阿里云服务器安全组设置规则分享,阿里云服务器安全组如何放行端口设置教程
6907 0
【大创_社区划分】——PageRank算法的解析与Python实现
一、什么是pagerank PageRank的Page可是认为是网页,表示网页排名,也可以认为是Larry Page(google 产品经理),因为他是这个算法的发明者之一,还是google CEO(^_^)。
1033 0
使用OpenApi弹性释放和设置云服务器ECS释放
云服务器ECS的一个重要特性就是按需创建资源。您可以在业务高峰期按需弹性的自定义规则进行资源创建,在完成业务计算的时候释放资源。本篇将提供几个Tips帮助您更加容易和自动化的完成云服务器的释放和弹性设置。
7751 0
算法笔试模拟题精解之“能量半径”
题目的含义就是找到距离原点最近的第k个点,并求它的半径。这个题的关键在于排序算法。使用最简单的冒泡排序,时间复杂度O(n^2);使用快速排序等好一点的排序算法,时间复杂度O(nlog(n));也可以使用java中Arrays类中的sort函数。
346 0
算法题——投篮比赛获胜概率问题
问题描述: 甲乙两人比赛投篮。约定甲先投篮,每人投篮投进一球,则继续投球,若投失一球,则换人投球。初始积分为1分,甲每投进一球,积分加1分;乙每投进1球,积分减1分。若积分达到N分(N>1),甲获胜;若积分减至0分,乙获胜。
733 0
560
文章
1795
问答
来源圈子
更多
+ 订阅
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载