A*****o
发帖数: 102 | 1 参加了一个面试，一道算法题是这样的，我没有做出来，大家帮我看看，我觉得好难。
题目根据回忆是这样的：
发牌人手上有52张扑克牌，在一个初始化好了的数组里面（已经知道牌的点数，J,Q,K
价值是 10，A 比较特殊可以 价值 1，也可以价值 11），发牌人自己能看见数组里牌
的点数和顺序，另外有四个人，发牌人可以把数组里面的牌一张一张的按照数组里的顺
序发给四个人中的任何一个（条件是这个人拿了这张牌后，他手中的牌点数之和小于等
于21），牌必须按照初始化好的数组里面的顺序发，发牌人想把一张牌发给4个人中的
谁就发给谁。发牌人也可以选择丢掉这张牌，不发给任何人。 如果当前4个人，拿了这
张牌，手上点数都大于21，那么发牌人必须把这张牌扔掉。任何人，手上的牌，点数之
和达到21点后，得把手上的所有牌扔掉，算成功达到21点一次，他又可以开始接牌。请
给发牌人设计一种算法（每张牌发给谁，还是丢掉），让4个人产生的21点成功次数总
和最多。 不涉及任何概率的问题，因为数组里的牌是已知的。
输入：数组，52个元素代表52张牌
要求输出：
（1） 整数的一维数组，52个元素，0代表丢掉了，1代表给了第一个人，2代表
给了第二个人，3代表给了第三个人，4代表给了第四个人
（2） 总共产生了几次21点
面试的时候，死在这道题上面，其他的题目都做对了，感觉这是离offer最近的一次。
郁闷死了！ |
b********6
发帖数: 35437 | |
h*********n
发帖数: 11319 | 3 哪家？
K
【在 A*****o 的大作中提到】
: 参加了一个面试，一道算法题是这样的，我没有做出来，大家帮我看看，我觉得好难。
: 题目根据回忆是这样的：
: 发牌人手上有52张扑克牌，在一个初始化好了的数组里面（已经知道牌的点数，J,Q,K
: 价值是 10，A 比较特殊可以 价值 1，也可以价值 11），发牌人自己能看见数组里牌
: 的点数和顺序，另外有四个人，发牌人可以把数组里面的牌一张一张的按照数组里的顺
: 序发给四个人中的任何一个（条件是这个人拿了这张牌后，他手中的牌点数之和小于等
: 于21），牌必须按照初始化好的数组里面的顺序发，发牌人想把一张牌发给4个人中的
: 谁就发给谁。发牌人也可以选择丢掉这张牌，不发给任何人。 如果当前4个人，拿了这
: 张牌，手上点数都大于21，那么发牌人必须把这张牌扔掉。任何人，手上的牌，点数之
: 和达到21点后，得把手上的所有牌扔掉，算成功达到21点一次，他又可以开始接牌。请
|
c*******t
发帖数: 1095 | 4 试试dp
num[i] = 第i张牌面额
F[i][p1][p2][p3][p4] = 从第i张牌开始， person1 的点数为p1, person2 的点数为
p2 ... person4的点数p4的状态 是能最多达到21的次数
= max(
F[i+1][p1][p2][p3][p4], // 弃牌
F[i+1][p1 + num[i+1]][p2][p3][p4] if p1 + num[i+1] < 21
F[i+1][0][p2][p3][p4] + 1, if p1 + num[i+1] == 21
... p2 , p3, p4 依次类推
)
return F[0][0][0][0][0].
想了想这个感觉基本就像是brute force了 runtime (52* 21^4), space (21^4) |
d******c
发帖数: 2407 | 5 既然顺序随机，我不觉得有什么聪明算法，也就是BFS了，尽量通过剪枝来减少搜索空
间。
21这个数字不大，能用牌组合成21点的情况是有限的，先穷举出来。
如果这52张牌是完整一套，也就是4种花色每种13张，那么你的牌种类有限，上面所有
组合里可以筛掉一大部分（比如需要5张2的）
搜索开始以后，如果某人手里的牌是一个序列，那么根据你剩下的牌，只有某些组合才
能把它凑成21. 随着牌越来越少，很快会有人的牌再也凑不起来，可以忽略这个人。 |
R********n
发帖数: 3601 | 6 哪家这么变态
K
【在 A*****o 的大作中提到】
: 参加了一个面试，一道算法题是这样的，我没有做出来，大家帮我看看，我觉得好难。
: 题目根据回忆是这样的：
: 发牌人手上有52张扑克牌，在一个初始化好了的数组里面（已经知道牌的点数，J,Q,K
: 价值是 10，A 比较特殊可以 价值 1，也可以价值 11），发牌人自己能看见数组里牌
: 的点数和顺序，另外有四个人，发牌人可以把数组里面的牌一张一张的按照数组里的顺
: 序发给四个人中的任何一个（条件是这个人拿了这张牌后，他手中的牌点数之和小于等
: 于21），牌必须按照初始化好的数组里面的顺序发，发牌人想把一张牌发给4个人中的
: 谁就发给谁。发牌人也可以选择丢掉这张牌，不发给任何人。 如果当前4个人，拿了这
: 张牌，手上点数都大于21，那么发牌人必须把这张牌扔掉。任何人，手上的牌，点数之
: 和达到21点后，得把手上的所有牌扔掉，算成功达到21点一次，他又可以开始接牌。请
|
h*********2
发帖数: 444 | |
