面试题61：扑克牌中的顺子

把大小王视为0，排序后拒绝非零重复并累计相邻空缺，用万能牌预算判定五张牌能否组成顺子。

学习目标

  • 能用排序后"非零重复 + 相邻空缺"两步判定五张牌是否为顺子
  • 能解释万能牌预算（空缺数 ≤ 王数）为什么是充要条件
  • 能说明 A 按 1 参与判定与边界输入（不足五张/超范围）的处理

从“一张王能补哪一个位置”开始

抽到0、3、2、6、4时，0可以代表5，重排后得到2、3、4、5、6；抽到0、3、1、6、4时，非零牌之间同时缺2和5，一张王只能补一个位置，因此失败。

这道“”不是寻找最长连续子序列，而是问固定的五张牌能否重新排列并把大小王替换成合适点数，使最终五个点数连续。

作者约定2到10使用数字本身，A为1，J为11，Q为12，K为13，并让“”。0是一张；有两个0就有两次替换机会，不能把一张王同时补两个缺口。

rank⁡(A)=1,rank⁡(J)=11,rank⁡(Q)=12,rank⁡(K)=13,rank⁡(joker)=0\operatorname{rank}(A)=1,\quad \operatorname{rank}(J)=11,\quad \operatorname{rank}(Q)=12,\quad \operatorname{rank}(K)=13,\quad \operatorname{rank}(\text{joker})=0
排序聚 0，再数空缺：王的张数 ≥ 空缺总数即顺子原始抽牌顺序（点击上方按钮切换牌组）03264排序排序后：0（王）聚左，非零牌递增02346非零牌在数轴上的空缺：共 1 处2346空缺 = 1，王 = 1 → 恰好补齐，是顺子条件：空缺数 ≤ 王数，且无非零对子。
排序把所有 0 聚到左侧，也让重复牌与相邻空缺能够一次线性扫描发现；点击按钮可切换牌组验证判定。

先预测排序后0的数量和非零空缺，再判断结果。不要先套“最大值减最小值不超过4”，因为全0、重复牌和都会让未经定义的下标或错误前提混进判断。

排序把三个问题同时显露出来

作者调用qsort原地。排序后的0全部聚在左侧，非零牌递增排列；于是一次扫描就能完成三件事：

  1. 从头统计连续0的数量。
  2. 比较相邻，相等立即失败。
  3. 把相邻差值减1累加，得到需要万能牌填补的位置数。
分步1 / 3

排序聚 0

排序后所有 0（大小王）聚到左侧，非零牌递增排列。统计连续 0 的数量，得到万能牌预算上限。

排序聚 0，再数空缺：王的张数 ≥ 空缺总数即顺子原始抽牌顺序（点击上方按钮切换牌组）03264排序排序后：0（王）聚左，非零牌递增02346非零牌在数轴上的空缺：共 1 处2346空缺 = 1，王 = 1 → 恰好补齐，是顺子条件：空缺数 ≤ 王数，且无非零对子。
排序把所有 0 聚到左侧，也让重复牌与相邻空缺能够一次线性扫描发现；点击按钮可切换牌组验证判定。

这种先统一顺序再做局部判定的过程称为。原抽牌顺序与顺子是否成立无关，但排序会修改调用者传入的数组，这是作者接口可见的副作用。

如何由相邻差得到

设排序后有r张互不相同的非零牌，依次为x1到xr。相邻两张之间缺少的整数个数是后一张减前一张再减1；全部相加就是。

G=∑i=1r−1(xi+1−xi−1)=xr−x1−(r−1)G=\sum_{i=1}^{r-1}(x_{i+1}-x_i-1) =x_r-x_1-(r-1)

例如排序结果0、0、1、3、5的相邻空缺是1到3之间缺2、3到5之间缺4，总空缺G等于2；两个0恰好替换2和4。

排序结果王的数量需要填的空缺预算结论结果
0,2,3,4,61缺 5，共 1刚好补齐true
0,1,3,4,61缺 2、5，共 2预算不足false
0,0,1,3,52缺 2、4，共 2刚好补齐true
0,0,0,1,53缺 2、3、4，共 3刚好补齐true
0,0,0,1,73缺 2..6，共 5预算不足false
0,0,0,1,13非零牌重复不能用王消除对子false
0 只能填缺失点数，不能让两张相同非零牌同时出现在一条顺子中。

令z为0的数量。每张王只能填一个内部空缺，因此通过条件是G不大于z。z就是。

如果预算有剩余，可以把多余的王放在非零区间左端或右端。例如0、0、0、0、3没有内部空缺，四张王可以组成1、2、4、5，最终得到1到5；不要求所有王都必须填在两张已有牌之间。

非零重复为什么必须先失败

顺子的每个点数只出现一次。若排序后相邻非零数字相等，例如0、0、0、1、1，即使有三张王也无法改变两张1本身；王可以补缺牌，不能删除或改写普通牌。

xi=xi+1⟹not a straightx_i=x_{i+1} \quad\Longrightarrow\quad \text{not a straight}

这就是原章规则“非零数字不能重复”。重复不能被当作“空缺为负一”参与求和，否则它可能抵消真正的正空缺，让错误输入看起来预算充足。

忠实还原作者实现

作者只拒绝空指针或length小于1，没有强制length等于5；算法本身确实可以判断任意正长度的“可否补成同长度连续整数”。但题面和全部正常测试都是五张牌，生产接口应明确是保留作者泛化行为，还是严格执行五张牌契约。

int Compare(const void* left,
            const void* right) {
    return *static_cast<const int*>(left)
         - *static_cast<const int*>(right);
}
 
bool IsContinuous(int* numbers, int length) {
    if (numbers == nullptr || length < 1)
        return false;
 
    qsort(numbers,
          length,
          sizeof(int),
          Compare);
 
    int numberOfZero = 0;
    int numberOfGap = 0;
 
    for (int i = 0;
         i < length && numbers[i] == 0;
         ++i) {
        ++numberOfZero;
    }
 
    int small = numberOfZero;
    int big = small + 1;
    while (big < length) {
        if (numbers[small] ==
            numbers[big]) {
            return false;
        }
 
        numberOfGap +=
            numbers[big]
          - numbers[small] - 1;
        small = big;
        ++big;
    }
 
    return numberOfGap <= numberOfZero;
}

当所有牌都是0时，numberOfZero等于length，small和big都位于末尾之后，但while条件立即为假，从未解引用numbers[small]，最终0个空缺不超过length张王，所以返回true。

旧页额外判断数组末项减去第一个非零项不超过4。这个条件在固定五张、非零互异时本来就由“空缺不超过0数量”推出，不仅冗余，还会在五张全0时访问arr[5]越界；旧TypeScript版本则因undefined参与计算而错误返回false。作者源码没有这个问题。

为什么空缺预算条件充要

必要性很直接：每个内部缺失点数都必须由不同的王占据，所以G不能大于z；非零重复也不可能出现在连续序列中。

充分性也成立：若非零牌互异且G不大于z，先用G张王填完x1到xr之间的全部缺口，已有区间就连续。剩余z-G张王依次放在区间两端，仍能保持整体连续。牌面边界是否允许扩展到1以下或13以上，应由题目契约限制；作者只把王称为任意数字，没有额外范围检查。

对于长度L、非零牌数量r和王数z，L等于r加z。由空缺公式可得到：

G≤z⟺xr−x1−(r−1)≤L−r⟺xr−x1≤L−1G\le z \quad\Longleftrightarrow\quad x_r-x_1-(r-1)\le L-r \quad\Longleftrightarrow\quad x_r-x_1\le L-1

所以固定五张且至少有一张非零牌时，“最大非零值减最小非零值不超过4”与“空缺数不超过王数”等价，前提仍然是非零牌不重复。两者无需同时写；同时写并不能增加正确性。

现代五张牌接口

题面固定抽5张，现代实现可以复制输入后排序，避免修改调用者；同时验证牌面在0到13内。作者的Compare通过两个int相减返回顺序，在合法牌面范围内安全，但若把函数泛化给任意int，减法可能溢出，违反qsort比较器契约。std::sort的比较函数直接使用小于关系更稳妥。

#include <algorithm>
#include <array>
#include <span>
 
bool isStraight(
    std::span<const int> cards) {
    if (cards.size() != 5)
        return false;
 
    std::array<int, 5> sorted{};
    std::copy(cards.begin(),
              cards.end(),
              sorted.begin());
 
    if (std::any_of(
            sorted.begin(),
            sorted.end(),
            [](int rank) {
                return rank < 0 || rank > 13;
            })) {
        return false;
    }
 
    std::sort(sorted.begin(), sorted.end());
 
    std::size_t first = 0;
    while (first < sorted.size() &&
           sorted[first] == 0) {
        ++first;
    }
 
    int gaps = 0;
    for (std::size_t i = first + 1;
         i < sorted.size();
         ++i) {
        if (sorted[i - 1] == sorted[i])
            return false;
        gaps += sorted[i]
              - sorted[i - 1] - 1;
    }
 
    const int jokers =
        static_cast<int>(first);
    return gaps <= jokers;
}

first等于5时，循环从6开始但不解引用数组，最终gaps为0、jokers为5，正确接受全王。若编码规范不希望无符号first加1越界，可先对first等于size的情况显式返回true，再进入循环。

A只按1参与作者判定

作者明确映射A为1，没有把A同时视为14。因此1、10、11、12、13不是顺子；排序后的空缺从1到10之间就有8个。

0、10、11、12、13可以成立，因为王可替换为9，得到9到13，并不需要把A解释为14。若产品规则要支持10、J、Q、K、A的皇家顺子，必须另写规则分支，不能悄悄改变作者的牌面映射。

维度作者实现结论工程边界
牌面映射A=1，2..10，J=11，Q=12，K=130 代表大小王不支持 A 同时作 14
作者长度指针非空且 length 大于 0可判断任意正长度题面实际固定抽 5 张
输入副作用qsort 原地排序调用后顺序改变现代接口可复制后排序
重复规则相邻非零值相同立即 false王不能消除对子全 0 没有非零重复
空缺规则所有相邻差减 1 后求和空缺不超过 0 数量剩余王可补区间两端
比较器用两个 int 相减普通牌面安全通用整数可能溢出
算法核心适用于任意长度，但固定五张牌、合法牌面和是否保留输入顺序属于接口契约。

作者也没有验证负数或大于13。对真实扑克牌接口，接受-2、-1、0、1、2并判成连续显然不合理；输入域校验应在算法前完成。

不排序的固定牌面解法

牌面只有0到13共14种，可用位集合记录非零牌是否出现，同时维护最小和最大非零点数。遇到重复立即失败；五张牌条件下，只要值域跨度不超过4，剩余王就足以补齐内部和两端。

#include <bitset>
#include <span>
 
bool isStraightLinear(
    std::span<const int> cards) {
    if (cards.size() != 5)
        return false;
 
    std::bitset<14> seen;
    int minimum = 14;
    int maximum = 0;
 
    for (int rank : cards) {
        if (rank < 0 || rank > 13)
            return false;
        if (rank == 0)
            continue;
        if (seen.test(rank))
            return false;
 
        seen.set(rank);
        minimum = std::min(minimum, rank);
        maximum = std::max(maximum, rank);
    }
 
    return maximum == 0 ||
           maximum - minimum <= 4;
}

这个版本时间O(L)、额外空间O(1)，其中L固定为5；排序版时间O(L log L)。在本题常量规模下性能差异没有实际意义，作者排序版更直接展示“统计相邻数字空缺”的推理，因此应先掌握原解，再把位集合视为等价优化。

作者12组测试逐项覆盖

作者的Test会先调用IsContinuous，再与expected布尔值比较并打印Passed或Failed。Test1到Test10覆盖从0张到5张王、预算恰好与不足；Test11专门检查非零对子；Test12传空指针和长度0做鲁棒性测试。

边界最有价值的是Test9与Test10：3加四张王返回true，全为0也返回true。它们证明“没有相邻非零牌”不是失败，剩余王可以自由构造一段连续值。

作者没有测试非法牌面、非5长度、输入是否被排序修改、A高位顺子规则和比较器极值。若实现选择严格五张牌接口，应为这些契约单独加断言，不能拿作者的任意正长度行为当作题面要求。

#include <array>
#include <cassert>
 
void testStraightContract() {
    assert(isStraight(
        std::array{1, 3, 2, 5, 4}));
    assert(!isStraight(
        std::array{1, 3, 2, 6, 4}));
    assert(isStraight(
        std::array{0, 3, 2, 6, 4}));
    assert(!isStraight(
        std::array{0, 3, 1, 6, 4}));
    assert(isStraight(
        std::array{0, 0, 0, 0, 0}));
    assert(!isStraight(
        std::array{1, 0, 0, 1, 0}));
    assert(!isStraight(
        std::array{-1, 0, 1, 2, 3}));
    assert(!isStraight(
        std::array{1, 10, 11, 12, 13}));
}

还可以对所有0到13的五元组做穷举，让排序版与位集合版对拍。14的5次方约53.8万，测试规模很小；这比只举几个手写例子更能发现重复、全王和值域边界的分歧。

本章练习

练习

问题 1： 判定顺子的两步是什么？为什么顺序不能反？

问题 2： 0、3、2、6、4 为什么是顺子，而 0、3、1、6、4 不是？

问题 3： 除常规五张牌外，还需防御哪些边界输入？

问题 4： 五张全为 0（大小王）时，程序应返回什么？为什么旧的"max-min≤4"判断会出错？

本章回顾

  1. 扑克牌中的顺子允许重排，普通牌映射1到13，大小王作为0。
  2. 排序后先数0，再拒绝非零重复，最后统计相邻数字空缺。
  3. 每个0提供一份替代预算，空缺总数不超过0数量即可补齐。
  4. 剩余王可以放在已有连续区间两端，因此无需恰好耗尽预算。
  5. 固定五张时，非零互异前提下，空缺条件等价于最大最小非零值之差不超过4。
  6. 作者原地qsort并接受任意正长度；严格题面接口应固定5张、验证0到13并避免修改输入。
  7. 全为0应返回true；旧页额外首尾判断会越界或误判。
  8. A在作者规则中只等于1，皇家顺子需要独立契约。
  9. 作者12组测试覆盖王数、空缺、对子和空指针，仍需补输入域与接口测试。

名词解释

名词解释

本章出现的专业名词，用大白话再讲一遍。

顺子
五张点数连续递增的牌组，大小王可替换为任意点数。
万能牌
大小王（点数 0），可以补任意一个缺失点数。
空缺数
排序后相邻非零牌之间缺失的点数位置数，由相邻差减 1 得到。
排序
把牌面按点数升序排列，使 0 聚左、非零递增，便于一次扫描完成统计。
边界输入
牌数不足五张、点数超范围等异常输入，需要按合同明确定义行为。
总空缺数
所有相邻非零牌之间缺失点数之和，由各相邻差减 1 累加得到。
复习本章（5 题）

讨论

评论区加载中…