面试题61. 扑克牌中的顺子

题目

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

思路

5张牌形成顺子的充分条件是：

（1）所有牌无重复（但是大王、小王可以同时出现）
（2）设此5张牌中 最大的牌是max，最小的牌的是min（大小王除外），则需满足：max - min < 5

因此可以将问题转化成：此5张牌是否可以满足以上两个条件？

方法一：集合Set + 遍历

• 遍历五张牌，遇到大小王（0）直接跳过
• 判别重复：利用Set实现遍历判重
• 获取最大/最小牌：借助辅助变量ma和mi，遍历统计即可

算法流程如下：

java代码如下：

class Solution{public boolean isStraight(int[] nums){Set<Integer> 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;//如果有重复，提前返回falserepeat.add(num);//添加到Set}return max - min < 5;//判断是否可以构成顺子}
}

方法二：排序 + 遍历

• 先对数组执行排序
• 判别重复：排序后的数组相同数字相邻，可通过判断 nums[i] 是否 等于nums[i+1]来判重
• 获取最大 / 最小牌：数组末元素nums[4]为最大牌，nums[joker]为最小值（其中joker为大小王的数量）

算法流程如下：

java代码如下：

class Solution{public boolean isStraight(int[] nums){int joker = 0;Arrays.sort(nums);//数组排序for(int i = 0; i < 4; i++){if(nums[i] == 0){joker++;} else if(nums[i] == nums[i+1]){return false;//如果有重复，提前返回false}}return nums[4] - nums[joker] < 5;//最大牌 - 最小牌 < 5 即可构成顺子}
}