剑指 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