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

一、题目描述

若干副扑克牌中随机抽 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; 
    }
}

2、C++ 代码

class Solution {
public:
    bool isStraight(vector<int>& nums) {
        // 设置一个哈希表,将 nums 中的每一个元素都放入到哈希表 cards 中
        // 在 cards 中,每一个元素值仅允许出现一次
        unordered_map<int, int> cards;

        // 默认最小值为不可能存在的扑克牌值 14
        int mmin = 14;

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

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

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

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

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

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

            // 将这个扑克牌加入到哈希表 cards 中
            cards[num]++; 
        }

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

3、Python 代码

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

        # 设置一个哈希表,将 nums 中的每一个元素都放入到哈希表 cards 中
        # 在 cards 中,每一个元素值仅允许出现一次
        cards = set()

        # 默认最小值为不可能存在的扑克牌值 14
        mmin = 14

        # 默认最大值为不可能存在的扑克牌值 0
        mmax = 0

        # 遍历 nums
        for  num in  nums : 
            # num 为 0 ,说明是大小王,跳过它
            if num == 0 :  continue 

            # 否则说明 num 不为 0,需要更新 max 和 min

            # 更新最大值 max
            mmax = max(mmax, num) 

            # 更新最小值 min
            mmin = min(mmin, num) 

            # 如果发现 cards 已经存在了 num,那么说明 nums 中存在了重复的扑克牌,必然无法组成顺子
            if num in cards :  return False

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


        # 遍历结束后,查看最大牌和最小牌的差值是否小于 5
        # 如果是小于 5,则可构成顺子
        # 反之,无法构成顺子
        return mmax - mmin < 5