算法的问题:从扑克牌中随机抽 5 张牌,判断是不是一个顺子,即这 5 张牌是连续的,JQK 用 11、12、13 表示。(不考虑大小王和花色
我的思路是:
这里有一个问题。。没有考虑特殊情况 10JQKA。
请教一下,应该如何判断这个特殊的边界问题比较好?
1
whileFalse 2018-09-12 11:07:44 +08:00
所以到底是要做什么?有什么资源限制?
|
2
tux 2018-09-12 11:28:28 +08:00
那就把 A 替换成 14
|
3
xubeiyan 2018-09-12 11:32:01 +08:00 via Android
不考虑花色的话,顺子一共的牌型才 10 种( A2345-10JQKA ),检查在不在这 10 种排型里面就是了
|
4
princelai 2018-09-12 11:37:26 +08:00
判断两次,(sum%5==0 and max-min==4) or (sum==47 and max-min==12),我随便写的,没验证过
|
5
Bryan0Z 2018-09-12 11:47:47 +08:00 via Android
这有啥难的,先排序,然后,A2345678910JQKA 顺着比较就行了
|
6
moresteam 2018-09-12 11:50:06 +08:00 via Android
直接穷举可不可以呢
|
7
xenme 2018-09-12 11:52:49 +08:00
sort,然后逐个检查就行了。
这么简单的问题。 又不是让你排一百万,限制你的算法复杂度啥的。 |
8
dongxiaozhuo 2018-09-12 14:06:34 +08:00
随便瞎猜的:
把 A 换成 14。顺子就是等差为 1 的等差数列。上限为 5 张,遍历一次拿到最大值,最小值,同时计算数列的和 (sum) 。然后用等差数列的公式,用最大值、最小值、count、等差值算出理论值,与数列的和对比,如果相等,就是顺子,如果不相等,就不是顺子。 时间上是一次遍历,很短,同时没有排序。空间上使用 5 个变量:最大值、最小值、和、等差数列和、长度。 |
11
orqzsf1 OP @dongxiaozhuo 把 A 换成 14,12345 这样情况怎么处理?
|
13
mbtfdwlx 2018-09-12 14:20:47 +08:00 1
我也推荐 7L 的做法。同时,把 A 的牌换成 14。再 check 一次。 首先这样做肯定算法时间复杂度是最高的。但是好处也多
1.易读性强。其他人读你的算法一读就知道是干嘛的。 2.兼容性更强。你要判断 5 张牌 差是 4。如果后续开发需要判断 3 张牌呢?是不是要多传一个参数?所以逐一排查就更方便。 3.优化空间更大。排序的算法可以在顺子算法之外做。只要保证传进的数组是有序的就可以。所以不需要每次都在判断顺子的函数内排序。 |
14
mbtfdwlx 2018-09-12 14:23:16 +08:00
补充一下 不如 A78910 五张牌,先 check 1 78910。再 check78910 14 只要一个满足条件就是顺子 没有 A 的牌只需要检查一次
|
15
orange1818 2018-09-12 14:29:08 +08:00
function checkShunzi(arr, min, max) { //思路圆环
arr = arr.sort(); if (isShunNum(arr)) { return true; } //如果不是 123456 这种,而是 9012 这种,那么剩余的 345678 是 shunNum,就判断剩余的号码是不是 shunNum const restArr = []; for (let i = min; i < max; i++) { if (arr.indexOf(i) === -1) { restArr.push(i); } } return isShunNum(arr); function isShunNum(arr) { return arr.every(function (item, index, arr) { return 0 === index || item - 1 === arr[index - 1]; }) } } |
16
dongxiaozhuo 2018-09-12 14:30:40 +08:00 1
@orqzsf1
给 A 一个特殊属性,遇到 A 的时候,开启特殊计算,需要分别计算 1 和 14 的情况。 我理解,如果是扑克牌游戏的话,以后是 5 张,还是 10 张很难说。用 7L 的排序也可以,简单明了一些。 |
18
mangoDB 2018-09-12 14:42:32 +08:00
> 设有 N 张牌,长度为 N 的数组模拟一个 [首尾相连] 的 [环] 。
1. 每次取 X 张牌( X<N ),然后分别在环上对应节点进行标记。 2. 遍历整个环,当 gap 数等于 2 时,X 张牌为顺子。 |
20
dongxiaozhuo 2018-09-12 15:26:37 +08:00
@mangoDB 首尾相连的环,有一个问题是,会出现 [11, 12, 13, A, 2] 和 [12,13,A,2,3] 这样的顺子,看起来不一定预期想要的结果吧?
|
21
teslayun 2018-09-12 16:50:10 +08:00
最近刚好在弄个斗地主,我这判断是顺子的方法是,先把选择的牌(数组)从大到小排序(且数组大于 5 ),然后在 for 循环,判断数组第 i 张减去第 i+1 张是否等于 1。
|
22
0x11901 2018-09-12 18:16:09 +08:00
……大哥,高中数学了解一下……
既然你已经有了第一步——判断是否重复,重复则一定不是顺子 那么 A 用 14,2 用 15 表示。是否是顺子,其实可以看作是否是公差为 1 的等差数列,如果是那么必然满足等差数列通项公式:$$ \ a_n=a_1+(n-1)d $$ 所以你只需要找到首项、尾项和 n 就行了,公差 d 为 1 …… 代码用 cpp 吧你将就看一下吧: ```cpp bool isContinuous(const std::vector<size_t> &vector) { return *max_element(vector.begin(), vector.end()) - *min_element(vector.begin(), vector.end()) == (vector.size() - 1) * 1; } bool isContinuous(size_t a_1, size_t a_n, ssize_t n) { return a_n - a_1 == (n - 1) * 1; } ``` |
23
sampeng 2018-09-12 19:49:28 +08:00
如果是业务用。。我就直接怼枚举。一起就 10 个。。枚举最快最简单。
简单才是最好的。。 |
24
kootain 2018-09-12 19:49:51 +08:00 via Android
长度 5 的循环队列,第一张牌插入的时候从 0 开始,之后就是和 0 位置的差值,决定插入位置。如果队列有重复插入不成顺,反之成顺。
上面说排序的先考虑一下排序的复杂度,然后拍完序又要遍历一遍,不是最优解。 |