P2850. 斗地主之顺子

解题思路

题意理解与补充

题目描述非常不清楚，对于一些特殊情况没有详细说明。只能够通过考试过程中自行理解测试并进行优化。本篇题解最终呈现的代码能够通过 95% 的用例。

例子 1 输入：3 4 5 6 7 4 5 6 7 8 9 10 J 实际考试中，实测应该要求输出：

而不是：

这个例子说明：当所给用例既可以凑成单个长顺子或者多个顺子的时候，应该优先凑成多个顺子。

例子 2 输入：3 4 5 6 7 3 4 5 6 7 A A A 实际考试中，实测应该要求输出：

而不是：

这个例子说明：每一张牌只可以使用一次，但如果能够凑出多个顺子需要尽量去使用。

例子 3 输入：3 4 5 6 7 3 4 5 6 7 8 A A 实际考试中，实测应该要求输出：

而不是：

这个例子说明：当出现多个顺子的起始位置相等的时候，应该先输出长度更短的顺子。

上述几点在题目中都没有说明，只能根据具体的代码通过比例情况来反推。

另外，由于题目指出输入的牌数一定是 13 张牌，这意味着输出的顺子数量一定只有 1 个或者 2 个（即输出的行数只有 1 行或者 2 行）。

---

利用哈希表求下一张牌

如果顺子都是数字，那么处理顺子问题就非常方便。假设某张牌对应的数字是 num，那么其下一张牌就是 num + 1。

但题目有一个较难处理的地方，是牌为 J、Q、K 和 A 的情况。为了应对字母和数字混合出现的情况，我们可以构建一个哈希表 next_card_dic。

实际上，next_card_dic 就是形如以下结构的哈希表：

如果我们知道当前卡牌是 card，card 是顺子中的一张牌，那么下一张牌就是 next_card_dic[card]。这个哈希表不大，手动构建也行。

---

利用哈希表统计牌数

在前面题意理解中提到，每一张牌只能够使用一次。所以我们可以用一个哈希表计数器 card_cnt 来统计每一张牌各有多少张，并且在凑成顺子之后减去这些牌的数量要相应减少。

---

枚举初始牌的框架

在初始化 card_cnt 之后，我们就可以计算顺子了。因为最大且最短的顺子是 10 J Q K A，显然顺子的第一张牌的范围是 3 到 10。我们可以枚举初始牌 start 的范围为 3 到 10，如果我们使用 start 作为顺子的初始牌，能否构建出顺子。

因此可以构建出如下的代码框架：

在后面的讲解我们会看到，check() 函数是用于计算特定顺子是否存在的函数。如果以 start 为起始牌的顺子存在，则 check() 函数会返回 True，否则将返回 False。返回的结果会传参给 flag。

由于可能出现多个顺子均为同一个 start 的情况，如例子 3 4 5 6 7 3 4 5 6 7 A A A 要求输出两个顺子 3 4 5 6 7 和 3 4 5 6 7，因此如果计算出 flag 为 True 的时候，我们仍然不能排除 start 仍可能作为初始牌的情况。因此只有当 `flag` 为 `False` 的时候，我们才递增 `start`。

---

计算特定顺子的函数

假设我们想知道，以某张牌 start 作为起始牌的顺子是否存在以及这个顺子是什么，我们可以构建如下的一个 check() 函数。

其中 ans 为储存最终答案的二维列表。我们将这个以 start 为起始牌的顺子储存在列表 res 中。5 是顺子的最小长度。

这里我们只循环 5 次的原因在于，这个顺子虽然可能不止这么长，但是为了尽可能多地凑出更多顺子，我们先暂时凑出长度为 5 的顺子，然后在所有顺子都考虑完毕之后，再考虑这些顺子能够进一步延长。

即对于例子 3 4 5 6 7 8 5 6 7 8 9 10 J，虽然其最终答案为 3 4 5 6 7 8 和 5 6 7 8 9 10 J，但在这一步我们必须先多凑出顺子，先算出两个长度为 5 的顺子 3 4 5 6 7 和 5 6 7 8 9，再在后续进一步延长这两个顺子得到最终答案。

---

顺子延长与输出

在起始牌 start 的 while 循环遍历结束之后，我们需要再次检查 ans 数组中的每一个长度为 5 的顺子是否还能够使用 card_cnt 中的牌进行延长。

可以再次抽象出函数 extend_res(res)，对单个顺子 res 进行延长。

其中 end_card 是当前顺子 res 中的最后一张牌。当 end_card 不为 "A"（为 "A" 则不存在下一张牌），且其下一张牌 next_card_dic[end_card] 的出现次数 card_cnt[next_card_dic[end_card]] 大于 0 时，则说明其下一张牌可以延长到当前顺子 res 中。

复杂度分析 设输入的牌数为 N（题面固定为 13 张），按代码结构逐段推导：

• 统计 Counter(cards) 为 O(N)；构建 next_card_dic 只有 11 个键值对，常数代价。
• 外层 while 枚举起始牌 start（3 到 10 共 8 种取值）：check() 每次严格循环至多 5 次，是常数代价；check() 返回 True 时 start 不递增，但每成功一次就从 card_cnt 中扣掉 5 张牌，13 张牌至多成功 2 次，所以 while 的总轮数不超过「8 次失败 + 2 次成功」，仍是常数级。
• 顺子延长 extend_res()：每张牌至多被加入某个顺子一次，全部顺子合计 O(N)。
• 最后对 ans 排序：由 13 张牌的约束，顺子最多只有 2 个，排序代价可以忽略。

综上，时间复杂度为 O(N)，在 N = 13 的固定规模下即常数级；空间复杂度为 O(N)，主要是计数器 card_cnt、下一张牌映射表与答案列表。