图解LeetCode——面试题61. 扑克牌中的顺子

一、题目

从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为0 ，可以看成任意数字。A 不能视为14。

二、示例

2.1> 示例 1:

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

2.2> 示例 2:

【输入】 [0,0,1,2,5]
【输出】 True

限制：

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

三、解题思路

根据题目描述，我们需要随机在衣服扑克牌中抽取5张牌，来判断是否可以构成顺子。而其中大小王可以是任意的数字。那么针对题目描述，假设选取的5张牌是顺子的话，我们大致可以推理出如下两种情况：

【情况1】5张牌中没有大小王，那么这五张牌就是连续的数字，例如：9、10、J、Q、K；
【情况2】5张牌中有大小王存在，那么除了大小王之外，手上的牌可能会出现不连续的情况，例如：9、10、K、大王、小王。当然，也可能出现连续的情况，例如：9、10、J、大王、小王；

那么如果我们把解题思路关注于大小王的总数，或者大小王在不同总数情况下，所处在5张牌的哪个位置可以保证构成顺子，那么解题思路就变得复杂起来了。其实有更好解题思路，就是，无论是否有大小王，那么手中的5张牌中，在不重复的前提下，除去大小王之后，最大牌与最小牌的差值一定是小于5的，那么就可以构成顺子。如下图所示：

3.1> 解题思路：排序 + 遍历

我们可以首先采用Arrays.sort(nums)对原数组nums进行排序，那么由于大小王是最小值，即：0。所以当我们从头开始遍历的时候，如果发现了值为0，则用joker去记录当前下标位置，当数组nums中所有的元素都遍历完毕后，执行最大牌（nums[4]）与最小非大小王牌（nums[joker + 1]）执行相减操作，如果小于5，则满足顺子。

3.2> 解题思路：排重校验 + 遍历

我们也可以不对原数组nums进行排序，而采用排重的方法。即：创建一个用于标记某张牌出现次数的mark数组，当发现某张牌（除大小王）出现次数大于0，则表示手中的5张牌中出现了重复，那么则直接可以判断不是顺子。

然后在遍历nums数组中非大小王牌时，更新手中最小牌min和手中最大牌max，当遍历完毕后，通过是否满足max - min < 5，来判断是否可以成为顺子。

四、代码实现

4.1> 排序 + 遍历

class Solution {
    public boolean isStraight(int[] nums) {
        Arrays.sort(nums);
        int joker = -1;
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == 0) joker = i;
            else if (nums[i] == nums[i+1]) return false;
        }
        return nums[4] - nums[joker + 1] < 5;
    }
}

4.2> 排重校验 + 遍历

class Solution {
    public boolean isStraight(int[] nums) {
        int[] mark = new int[14];
        int min = 14, max = -1;
        for (int num : nums) {
            if (num == 0) continue;
            if (mark[num] > 0) return false;
            mark[num]++;
            min = Math.min(min, num);
            max = Math.max(max, num);
        }
        return max - min < 5;
    }
}

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o)/ ~ 「干货分享，每天更新」