V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
orqzsf1
V2EX  ›  算法

请教一个关于扑克牌顺子的算法问题

  •  
  •   orqzsf1 · 2018-09-12 10:52:55 +08:00 · 4751 次点击
    这是一个创建于 2249 天前的主题,其中的信息可能已经有所发展或是发生改变。

    算法的问题:从扑克牌中随机抽 5 张牌,判断是不是一个顺子,即这 5 张牌是连续的,JQK 用 11、12、13 表示。(不考虑大小王和花色

    我的思路是:

    1. 判断是否重复,重复则一定不是顺子
    2. (最大的数字)-(最小的数字)!= 4 则不是
    3. 是顺子

    这里有一个问题。。没有考虑特殊情况 10JQKA。

    请教一下,应该如何判断这个特殊的边界问题比较好?

    24 条回复    2018-09-12 19:49:51 +08:00
    whileFalse
        1
    whileFalse  
       2018-09-12 11:07:44 +08:00
    所以到底是要做什么?有什么资源限制?
    tux
        2
    tux  
       2018-09-12 11:28:28 +08:00
    那就把 A 替换成 14
    xubeiyan
        3
    xubeiyan  
       2018-09-12 11:32:01 +08:00 via Android
    不考虑花色的话,顺子一共的牌型才 10 种( A2345-10JQKA ),检查在不在这 10 种排型里面就是了
    princelai
        4
    princelai  
       2018-09-12 11:37:26 +08:00
    判断两次,(sum%5==0 and max-min==4) or (sum==47 and max-min==12),我随便写的,没验证过
    Bryan0Z
        5
    Bryan0Z  
       2018-09-12 11:47:47 +08:00 via Android
    这有啥难的,先排序,然后,A2345678910JQKA 顺着比较就行了
    moresteam
        6
    moresteam  
       2018-09-12 11:50:06 +08:00 via Android
    直接穷举可不可以呢
    xenme
        7
    xenme  
       2018-09-12 11:52:49 +08:00
    sort,然后逐个检查就行了。
    这么简单的问题。

    又不是让你排一百万,限制你的算法复杂度啥的。
    dongxiaozhuo
        8
    dongxiaozhuo  
       2018-09-12 14:06:34 +08:00
    随便瞎猜的:
    把 A 换成 14。顺子就是等差为 1 的等差数列。上限为 5 张,遍历一次拿到最大值,最小值,同时计算数列的和 (sum) 。然后用等差数列的公式,用最大值、最小值、count、等差值算出理论值,与数列的和对比,如果相等,就是顺子,如果不相等,就不是顺子。

    时间上是一次遍历,很短,同时没有排序。空间上使用 5 个变量:最大值、最小值、和、等差数列和、长度。
    orqzsf1
        9
    orqzsf1  
    OP
       2018-09-12 14:09:50 +08:00
    @tux A 换成 14,那 12345 呢,142345 这样?
    orqzsf1
        10
    orqzsf1  
    OP
       2018-09-12 14:10:19 +08:00
    @moresteam 穷举当然可以,看看有没有更好的解法
    orqzsf1
        11
    orqzsf1  
    OP
       2018-09-12 14:11:34 +08:00
    @dongxiaozhuo 把 A 换成 14,12345 这样情况怎么处理?
    orqzsf1
        12
    orqzsf1  
    OP
       2018-09-12 14:12:30 +08:00
    @Bryan0Z 能否详细说下如何顺着比较?
    mbtfdwlx
        13
    mbtfdwlx  
       2018-09-12 14:20:47 +08:00   ❤️ 1
    我也推荐 7L 的做法。同时,把 A 的牌换成 14。再 check 一次。 首先这样做肯定算法时间复杂度是最高的。但是好处也多
    1.易读性强。其他人读你的算法一读就知道是干嘛的。
    2.兼容性更强。你要判断 5 张牌 差是 4。如果后续开发需要判断 3 张牌呢?是不是要多传一个参数?所以逐一排查就更方便。
    3.优化空间更大。排序的算法可以在顺子算法之外做。只要保证传进的数组是有序的就可以。所以不需要每次都在判断顺子的函数内排序。
    mbtfdwlx
        14
    mbtfdwlx  
       2018-09-12 14:23:16 +08:00
    补充一下 不如 A78910 五张牌,先 check 1 78910。再 check78910 14 只要一个满足条件就是顺子 没有 A 的牌只需要检查一次
    orange1818
        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];
    })
    }
    }
    dongxiaozhuo
        16
    dongxiaozhuo  
       2018-09-12 14:30:40 +08:00   ❤️ 1
    @orqzsf1

    给 A 一个特殊属性,遇到 A 的时候,开启特殊计算,需要分别计算 1 和 14 的情况。

    我理解,如果是扑克牌游戏的话,以后是 5 张,还是 10 张很难说。用 7L 的排序也可以,简单明了一些。
    tux
        17
    tux  
       2018-09-12 14:41:26 +08:00
    @orqzsf1 A 换成 14,换之前判断一次,换之后再判断一次,2 种情况其实都是顺子吧?
    mangoDB
        18
    mangoDB  
       2018-09-12 14:42:32 +08:00
    > 设有 N 张牌,长度为 N 的数组模拟一个 [首尾相连] 的 [环] 。
    1. 每次取 X 张牌( X<N ),然后分别在环上对应节点进行标记。
    2. 遍历整个环,当 gap 数等于 2 时,X 张牌为顺子。
    orqzsf1
        19
    orqzsf1  
    OP
       2018-09-12 14:58:08 +08:00
    @mbtfdwlx 明白了,感谢!
    dongxiaozhuo
        20
    dongxiaozhuo  
       2018-09-12 15:26:37 +08:00
    @mangoDB 首尾相连的环,有一个问题是,会出现 [11, 12, 13, A, 2] 和 [12,13,A,2,3] 这样的顺子,看起来不一定预期想要的结果吧?
    teslayun
        21
    teslayun  
       2018-09-12 16:50:10 +08:00
    最近刚好在弄个斗地主,我这判断是顺子的方法是,先把选择的牌(数组)从大到小排序(且数组大于 5 ),然后在 for 循环,判断数组第 i 张减去第 i+1 张是否等于 1。
    0x11901
        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;
    }

    ```
    sampeng
        23
    sampeng  
       2018-09-12 19:49:28 +08:00
    如果是业务用。。我就直接怼枚举。一起就 10 个。。枚举最快最简单。
    简单才是最好的。。
    kootain
        24
    kootain  
       2018-09-12 19:49:51 +08:00 via Android
    长度 5 的循环队列,第一张牌插入的时候从 0 开始,之后就是和 0 位置的差值,决定插入位置。如果队列有重复插入不成顺,反之成顺。
    上面说排序的先考虑一下排序的复杂度,然后拍完序又要遍历一遍,不是最优解。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2558 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 15:33 · PVG 23:33 · LAX 07:33 · JFK 10:33
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.