2 u010759408 u010759408 于 2016.04.19 15:23 提问

一道算法或者逻辑面试题,求思路

100个面值是1-50随机分布的硬币排成一列,你和另一个人一人一个的取,只能从队列头部和尾部取。如何保证最后你取的硬币面值和比你对手多?

2个回答

lm_whales
lm_whales   Rxr 2016.04.19 15:43

保证你取倒数第二张?
还是和最大?
1~50 面值按照谁家的硬币?
美元?

美元面值:
现流通硬币有1 分、5 分、10分、1/4 元、1/2 元、1 元六种面值。
正面与背面所铸图案如下:
1 分 - 正面: Lincoln 林肯 ,背面:林肯纪念堂 5 分 - 正面:Jefferson 杰佛逊 ,背面:杰斐逊的故居

10分 - 正面: Roosevelt 罗斯福 ,背面:火炬,橄榄枝,橡树枝 1/4 元 - 正面:Washington 华盛顿 ,背面: 白头鹰
1/2 元 - 正面:Kennedy 肯尼迪 ,背面:总统专用国徽 1 元 - 正面:Sacagawea 莎卡嘉薇亚 ,背面:飞翔中的白头鹰
此外还发行过采用这六种面值的与上述图案不同的硬币,及5 分、10分、1/4 元、1/2 元、1 元面值的纪念币。
以前还发行过3分的硬币,现已不能流通。

人民币硬币面值
1分,2分,5分,(退出流通了)
1角,5角,1元(正在用):

既然是双端队列,你可以取走当期最大价值的,换成对手,也是如此,如果是求和的话,两种取法选最大,这是01背包
如果是最后一次面值最大,采用中间向两头扩展的办法从而保证能取到最大的

lm_whales
lm_whales 最优解那个,效率太低,可能会堆栈溢出,但求出的结果是最优结果。
一年多之前 回复
lm_whales
lm_whales 效率要高的多,但不一定是最优解
一年多之前 回复
lm_whales
lm_whales 有一个局部最优的方法,可是不能保证结果一定是最优的(可能 你获得超额利益,也可能对手,但是多数情况下,是最优的结果)
一年多之前 回复
lm_whales
lm_whales 有一个思路,但是效率太低了,我在考虑一下能否改进改进
一年多之前 回复
u010759408
u010759408 您好,最后是所有硬币和最大;硬币和人民币和美元没太大关系,取值从1-50即可;不知道是否能详细描述下思路,谢谢
一年多之前 回复
CSDNXIAOD
CSDNXIAOD   2016.04.20 08:41

一道javascript算法面试题
一道别致的算法面试题
网易有道的一道算法面试题
----------------------biu~biu~biu~~~在下问答机器人小D,这是我依靠自己的聪明才智给出的答案,如果不正确,你来咬我啊!

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!