剑指 Offer 61. 扑克牌中的顺子

大家好，我是吴师兄。

今天继续来学习《剑指Offer》系列的一道经典题目，依旧给出了非常详细的题解和精美的配图与动画。

一、题目描述

从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这 5 张牌是不是连续的。

2 ～ 10 为数字本身，A 为 1 ，J 为 11 ，Q 为 12 ，K 为 13 ，而大、小王为 0 ，可以看成任意数字。

A 不能视为 14。

示例 1:

输入: [1,2,3,4,5]
输出: True

示例 2:

输入: [0,0,1,2,5]
输出: True

限制：

• 数组长度为 5

• 数组的数取值为 [0, 13]

二、题目解析

5 张牌能否组成顺子，比如具备这个特征：5 张牌里面，除了大小王之外，所有牌均不重复，因为很显然，一旦有重复的牌，比如 1、2、2、3、4 这种牌型必然不是顺子。

除此之外，有以下几种情况：

1、5 张牌里面没有大小王。

最大牌和最小牌之差为 4，比如 1、2、3、4、5，最小牌为 1，最大牌为 5，两者之差为 4。

2、5 张牌里面有一个大小王，即出现过一个 0。

由于 0 可以看成任意数字，因此这个 0 可以变成任意的数字插在剩下的 4 张牌中的任意位置。

• 1、比如 0、4、5、6、7，里面 0 变成了 3，组成了 3、4、5、6、7 的顺子。
• 2、比如 4、5、6、7、0，里面 0 变成了 8，组成了 4、5、6、7、8 的顺子。
• 3、比如 3、0、5、6、7，里面 0 变成了 4，组成了 3、4、5、6、7 的顺子。

此时，可以注意到，除了 0 之外，最大牌与最小牌之差可能为 3 （ 情况 1、情况 2 ），也可能为 4 （ 情况 3 ）。

3、5 张牌里面有两个大小王，即出现过两个 0。

由于 0 可以看成任意数字，因此这两个 0 可以变成任意的数字插在剩下的 3 张牌中的任意位置。

• 1、比如 0、0、5、6、7，里面 0 变成了 3 和 4 ，组成了 3、4、5、6、7 的顺子。
• 2、比如 4、5、6、0、0，里面 0 变成了 7 和 8 ，组成了 4、5、6、7、8 的顺子。
• 3、比如 0、4、5、0、7，里面 0 变成了 3 和 6 ，组成了 3、4、5、6、7 的顺子。
• 4、比如 3、0、5、0、7，里面 0 变成了 4 和 6 ，组成了 3、4、5、6、7 的顺子。

此时，可以注意到，除了 0 之外，最大牌与最小牌之差可能为 2 （ 情况 1、情况 2 ），也可能为 3 （ 情况 3 ），也可能为 4（ 情况 4 ）。

由此可以看出，顺子的情况下除了 0 之外，五张牌的最大牌与最小牌之差必然是小于 5 的。

综上所述，我们可以去遍历这 5 张牌，执行如下的操作：

• 1、设置一个哈希表 Set，借助它来执行判重操作，判断这 5 张牌是否存在重复牌，如果存在，那么肯定就不是顺子了。
• 2、设置两个变量 Max、Min，用来记录这五张牌除了 0 之外的最大值和最小值。
• 3、遇到大小王，忽略它。
• 4、遇到非大小王的牌，检查哈希表是否存在这张牌，如果存在，那么肯定就不是顺子，直接返回 false，否则将它加入到哈希表中，同时更新最大牌、最小牌的值。
• 5、遍历完毕之后，判断 Max、Min 是否小于 5。

为了帮助你更好的理解整个过程，我特意做了一组动画，点开可以查看：

三、参考代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 剑指 Offer 61. 扑克牌中的顺子：https://leetcode-cn.com/problems/bu-ke-pai-zhong-de-shun-zi-lcof/
class Solution {
    public boolean isStraight(int[] nums) {

        // 设置一个哈希表，将 nums 中的每一个元素都放入到哈希表 cards 中
        // 在 cards 中，每一个元素值仅允许出现一次
        Set<Integer> cards = new HashSet<>();
        
        // 默认最小值为不可能存在的扑克牌值 14
        int min = 14;

        // 默认最大值为不可能存在的扑克牌值 0
        int max = 0;

        // 遍历 nums
        for(int num : nums) {
            // num 为 0 ，说明是大小王，跳过它
            if(num == 0) continue; 

            // 否则说明 num 不为 0，需要更新 max 和 min

            // 更新最大值 max
            max = Math.max(max, num); 

            // 更新最小值 min
            min = Math.min(min, num); 

            // 如果发现 cards 已经存在了 num，那么说明 nums 中存在了重复的扑克牌，必然无法组成顺子
            if(cards.contains(num)) return false;

            // 将这个扑克牌加入到哈希表 cards 中
            cards.add(num); 
        }

        // 遍历结束后，查看最大牌和最小牌的差值是否小于 5
        // 如果是小于 5，则可构成顺子
        // 反之，无法构成顺子
        return max - min < 5; 
    }
}