笔试算法模拟题精解之“Bob的花束”

简介: 本题充分理解题意后,直接模拟这个“选取最大值”的过程就可以得到结果了。

【在线编程产品介绍】

阿里云开发者社区在线编程:

免费刷题大神器,助你拿到好offer

周赛月赛不停歇,做题还能领奖品

大赛笔试全真题,常做常新有惊喜

点击链接开始产品体验:https://developer.aliyun.com/coding

本文为大家介绍的是“66题.Bob的花束”的解法探究。先来看一下题目内容:

题目详情:

等级:中等
知识点:贪心
查看题目:66.Bob的花束

Bob和Alice是青梅竹马。今天,Bob终于要鼓起勇气向Alice表白了!说到表白,自然是少不了买花了。Bob来到了花店,花店一共提供了9种花,每一种花都有对应的价钱。但是Bob的零花钱有限,不能把所有的花都买下来送给Alice。
为了方便挑选,Bob给这9种花分别标号1-9,Bob希望买到的花按照编号可以排出尽可能大数字,请问Bob能够排出的最大的数字是多少?
输入一个正整数value,代表Bob拥有的零花钱。(0<=value<=10^6)
和有9个数字的数组a,ai代表第i种花的价格。(1<=ai<=10^5,1<=i<=9)
输出一个数字,表示Bob可以排出的最大数字。如果Bob不能排出任何一个数字,则输出-1。
示例1
输入:
2
[9,11,1,12,5,8,9,10,6]
输出:
33
注意:
花店的每一种花都可以视为无限多。

解题方法:模拟选花过程

本题充分理解题意后,直接模拟这个“选取最大值”的过程就可以得到结果了。

首先,选取最大值,意味着首先这个结果的“位数”要足够多,比如假设所有的花价格都是1元钱,则11111111是花9块钱能买到的最大值,而不是333或者9这样的方案。这样相当于根据输入,输出的位数可以用很小的时间代价来确定:“用可用钱数,除以最便宜的花的价格,并向下取整”。假设这里的位数为m。

其次,在位数确定的情况下,高位数字越大,结果也就越大,比如同样是8元钱,只能购买价格为5的5号花,和价格为3的3号花时,购买35就是最差的方案,而53才是正确答案。而且因为每个花的数量是无限的,所以可以模拟这个 “从高位开始,逐个选取能买得起的最大的数字;同时每选完一位后,要确保剩下的钱,依旧可以买到m位数字的组合方案。”

提示: 根据上面逻辑写出的答案,在充分理解优化后,至少可以达到2遍扫描数组得到结果。

时间复杂度:O(9n)

看完是不是有了新思路了呢,快来试一下吧:查看题目:66.Bob的花束

在线编程周赛、月赛火热进行中,更有限时答题活动,社区定制卫衣、双肩背包等你来拿~每天都有好礼相送~点击了解周赛详情:在线编程内测中,抢先周赛赢好礼!面试考试前,快来刷刷题!

APPbanner784-312.png

上一篇: 笔试算法模拟题精解之“完美排列”
下一篇:笔试算法模拟题精解之“ 最优分组”的“遍历”解法

相关文章
|
6月前
|
算法 测试技术
进制算法题(进制转换、Alice和Bob的爱恨情仇)
进制算法题(进制转换、Alice和Bob的爱恨情仇)
|
6月前
|
算法 搜索推荐 Java
Java数据结构 -- 常见算法分析(查找算法、排序算法)精解详解!!!
Java数据结构 -- 常见算法分析(查找算法、排序算法)精解详解!!!
60 0
|
6月前
|
编解码 算法 前端开发
往年 | 大疆雷达算法校招笔试题目解析
往年 | 大疆雷达算法校招笔试题目解析
482 1
|
11月前
|
人工智能 算法 BI
C++二分查找算法:找到 Alice 和 Bob 可以相遇的建筑
C++二分查找算法:找到 Alice 和 Bob 可以相遇的建筑
|
算法
压缩算法 【腾讯2020校园招聘-后台&综合-第一次笔试 】
压缩算法 【腾讯2020校园招聘-后台&综合-第一次笔试 】
78 0
|
算法 网络协议
骚戴独家笔试---算法篇4
骚戴独家笔试---算法篇4
62 1
|
存储 算法
骚戴独家笔试---算法篇3
骚戴独家笔试---算法篇3
203 0
骚戴独家笔试---算法篇3
|
存储 算法
骚戴独家笔试---算法篇2
骚戴独家笔试---算法篇2
53 0
骚戴独家笔试---算法篇2
|
搜索推荐
7大排序算法-- 堆排 快速排序 --精解(下)
7大排序算法-- 堆排 快速排序 --精解(下)
84 0
|
搜索推荐
7大排序算法-- 堆排 快速排序 --精解(上)
7大排序算法-- 堆排 快速排序 --精解
52 0