📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 2348| 回复: 5
跳转到指定楼层
上一主题 下一主题
收起左侧

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

全局:

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

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)吗?

还请各位高手指点一下迷津啊

上一篇:问一题google foobar的题
下一篇:刷题刷到什么程度才能面试?
🔗
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 | 只看该作者
全局:
一次最大一次最小
即花费最少的保证找到(最大)的 解
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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