一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 435|回复: 5
收起左侧

[Leetcode] 求问一个leetcode题目:375. Guess Number Higher or Lower II

[复制链接] |试试Instant~ |关注本帖
WhatsFLAG 发表于 2016-10-15 00:44:11 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 WhatsFLAG 于 2016-10-15 00:56 编辑

如题,在做leetcode的时候,我发现自己理解这个问题的时候有点难度。

1.题目没有明确说目标值是多少,所以好像很类似于求期望值(但是follow up才是求期望,所以并不是)
2.HINT里面提到了 “The best strategy to play the game is to minimize the maximum loss you could possibly face. Another strategy is to minimize the expected loss. Here, we are interested in thefirst scenario.”
这里我很疑惑的地方是maximum loss you could possibly face,假如 [1, 2, 3],我的maximum loss could possibly face 不应该是(1+2)or (2+3)or(1+3)吗?假设每次我都猜错的话,对应于目标值是(3,1,2)
按这么理解岂不是答案应该是(1+2)吗?

还请各位高手指点一下迷津啊
keytion 发表于 2016-10-15 01:07:50 | 显示全部楼层
对于任何一个strategy, 都有一个worst case value. 然后让你选一个stratgegy, 是的这个worst case 最好。 Min-Max
回复 支持 反对

使用道具 举报

 楼主| WhatsFLAG 发表于 2016-10-15 01:13:23 | 显示全部楼层
keytion 发表于 2016-10-15 01:07
对于任何一个strategy, 都有一个worst case value. 然后让你选一个stratgegy, 是的这个worst case 最好。 M ...

那么以输入为3为例,有哪几种strategy啊
回复 支持 反对

使用道具 举报

stellari 发表于 2016-10-15 01:51:17 | 显示全部楼层
对于数列[1 2 3], 你有如下的猜测顺序:

[1 2] (如果2都错了,那不用再猜了,肯定是3), 这种策略最大付出是1+2=3
[1 3], 最大付出为1+3=4
[3 2], 最大付出5
[3 1], 最大付出4
[2] (2猜错时, 你会同时知道2是too low还是too high, 所以不用再猜了), 最大付出2

所以你现在要取这5个最大付出的最小值, 结果当然是2
回复 支持 反对

使用道具 举报

 楼主| WhatsFLAG 发表于 2016-10-15 03:08:42 | 显示全部楼层
本帖最后由 WhatsFLAG 于 2016-10-15 03:30 编辑

感谢各位的指点,我根据大家说的和自己的理解,Mark一下这个题的题意:

首先是开始的时候接收到很多变量,搞不清他们之间的关联,在这里梳理一下:
Key variables:

target,最优解,最大值,最小值,最坏情况

target并不是讨论固定一个数字,而是讨论在所有target的情况下(问题已经不是搜索元素,而是搜索一种空间或者状态了)

最坏情况,指的是 所有策略, 分别对应 所有target(最坏情况Max) 的可能性中最小的(最优解Min)

换句话说就是 对于任意的输入,有一种事先不确定的策略,但是他对于所有target进行游戏(最坏的情况下Max)都能超过(Min)其他的策略( 最坏的情况下Max)

所以实质就是 求最小策略 ,而策略大小的定义是对于所有target中最大的那个。

回复 支持 反对

使用道具 举报

wutongzhang 发表于 2016-10-16 16:17:05 | 显示全部楼层
一次最大一次最小
即花费最少的保证找到(最大)的 解
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-11 23:06

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表