查看: 3345| 回复: 10
跳转到指定楼层
上一主题 下一主题
收起左侧

[二分/排序/搜索] 最少出牌次数

全局:

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

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

x
QW是一名打牌小能手,现在他手里有n张牌,给定数组cards表示QW牌的点数,牌的点数范围为1~9,他想要用尽量少的次数把牌出完,请输出QW最少出牌次数
QW有以下三种出牌方式:
1.打出任意一张牌
2.打出两张及以上相同点数的牌
3.打出至少5张点数连续的牌(2,3,4,5,6是合法的而3,3,4,5,6,7是不合法的)

除了bf,想不到什么好的办法。。, 有思路的朋友麻烦给个提示,谢谢。

上一篇:给努力攒分看面经的新农分享点经验
下一篇:刷题经验和讲解整理
🔗
 楼主| geekzyj 2019-1-19 22:02:38 来自APP | 只看该作者
全局:
没有人吗?
回复

使用道具 举报

🔗
moluren 2019-1-19 22:30:31 | 只看该作者
全局:
特别不擅长这种题
回复

使用道具 举报

🔗
14417335 2019-1-24 02:40:37 | 只看该作者
全局:
加入一个STATE【】每个组合、最小花费 怎么样?这样可以prune掉一些更多的花费。
回复

使用道具 举报

🔗
14417335 2019-1-24 03:17:17 | 只看该作者
全局:
把所有的牌区分开来。按照至少5张点数连续的牌这一规则,说明其它牌和这些都不连着,可以单独BF处理。包括重复比如2,2,3,4,4,4,5,5,5,6,6,6,7可以计算出最小花费。每个区域的最小值加起来就是整体的最小值。
另外这个问题可以继续深化。比如
2,2,3,4,4,4,5,5,5,6,6,6,7

4,4,5,6,6,6,7,7,7,8,8,8,9
转化为A:2, B:1, C: 3, D: 3, E: 3, F: 1是同一个问题。也可以记忆。

递归关系。如果我打444,那么成本就转化为f(223)+f(5556667)+1

补充内容 (2019-1-24 03:52):
如果能够利用规则二和三,则不把规则一加入BF中。
回复

使用道具 举报

🔗
Enalynn 2019-1-24 03:43:34 | 只看该作者
全局:
基本上是暴力bfs, 先bucket,然后就慢慢搜。你会发现time limit 超时,这个时候你引入一个规则,就是如果不出顺子,比如把那张牌全出完。然后你的程序就过了。
回复

使用道具 举报

🔗
crlyw 2019-1-30 05:36:21 | 只看该作者
全局:
我原来想是贪心做,就是先打顺子,再打重复的,最后打单张,单手这样想有错误,lintcode86%的数据可以通过但是还有14%通过不了,看来要BFS试一试了

评分

参与人数 1大米 +2 收起 理由
Scala688 + 2 赞一个

查看全部评分

回复

使用道具 举报

🔗
Scala688 2019-1-30 06:04:48 | 只看该作者
全局:
crlyw 发表于 2019-1-30 05:36
我原来想是贪心做,就是先打顺子,再打重复的,最后打单张,单手这样想有错误,lintcode86%的数据可以通过 ...

请问利口猿啼号 是。。。 ?
回复

使用道具 举报

🔗
Scala688 2019-1-30 06:06:18 | 只看该作者
全局:
crlyw 发表于 2019-1-30 05:36
我原来想是贪心做,就是先打顺子,再打重复的,最后打单张,单手这样想有错误,lintcode86%的数据可以通过 ...

感觉是标准BFS。
回复

使用道具 举报

🔗
crlyw 2019-1-30 11:28:31 | 只看该作者
全局:
Scala688 发表于 2019-1-30 06:04
请问利口猿啼号 是。。。 ?

这个是lintcode的1672题,但是是ladder的好像搜索不到
回复

使用道具 举报

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

本版积分规则

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