关注下方公众号，分享硬核知识

  作者 | 小夕  出品 | 公众号：小夕学算法

题目

从扑克牌中随机抽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] .

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/bu-ke-pai-zhong-de-shun-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。


本题目中的顺子，只是代表从1开始的到13, 和现实玩牌的顺子有一点差别的就是，10 J Q K A 不构成本题目中的顺子：

思路

如果5张牌中无大小王

如果要构成是顺子的情况，那么必然需要连起来,比如像下图中的 1,2,3,4,5.

由于必须构成顺子，所以最大值5减去最小值1等于4，如果差值大于4，那么必然不是顺子了。

如果 5 张牌中有1个大小王

有一个大小王，也就是有一个数字 0，对于我们举的例子1,2,3,4,5,中有一个数字被 0进行替换了。

如果想要构成顺子，那么必须是1,2,3,4,5中的任意一个被0替换了，因为想要0可以变成任意的一个数字

1 被替换

除了0以为，最大差值5-2是3.

2 被替换

除了0以为，最大差值5-1是4.

3 被替换

除了0以为，最大差值5-1是4. ####4 被替换

除了0以为，最大差值5-1是4.

5 被替换

除了0以为，最大差值4-1是3.

上述5种情况，都是可以构成顺子的情况。

从上述 5 种情况可以看出来，只要是能构成顺子的情况，除了0以为，那么最大值和最小值差值必然小于等于4

如果 5 张牌中有2个大小王

总共有上述10种情况，观察这10种情况知道：

除了0以为，如果可以构成顺子，最大值，最小值的差必然小于等于 4.

思路总结

从上面的流程中可以知道本题的算法思路：

• 遍历5张牌，遇到是0的话直接跳过
• 遍历的时候有集合set把数存在里面，如果有重复，那么必然有对子，有对子必然无法变成顺子
• 用一个max 存最大值，有一个 min 存最小值，如果最后max和mix的差值小于等于4，那么说明是顺子。

动画

代码·

Python

class Solution:
    def isStraight(self, nums: List[int]) -> bool:
        repeat = set()
        ma, mi = 0, 14
        for num in nums:
            if num == 0: continue # 跳过大小王
            ma = max(ma, num) # 最大牌
            mi = min(mi, num) # 最小牌
            if num in repeat: return False # 若有重复，提前返回 false
            repeat.add(num) # 添加牌至 Set
        return ma - mi < 5 # 最大牌 - 最小牌 < 5 则可构成顺子 


Java

class Solution {
    public boolean isStraight(int[] nums) {
        Set repeat = new HashSet<>();
        int max = 0, min = 14;
        for(int num : nums) {
            if(num == 0) continue; // 跳过大小王
            max = Math.max(max, num); // 最大牌
            min = Math.min(min, num); // 最小牌
            if(repeat.contains(num)) return false; // 若有重复，提前返回 false
            repeat.add(num); // 添加此牌至 Set
        }
        return max - min < 5; // 最大牌 - 最小牌 < 5 则可构成顺子
    }
}


C

class Solution {
public:
    bool isStraight(vector