61. 扑克牌中的顺子
61. 扑克牌中的顺子
题目
展览馆展出来自 13
个朝代的文物,每排展柜展出 5
个文物。某排文物的摆放情况记录于数组 places
,其中 places[i]
表示处于第 i
位文物的所属朝代编号。其中,编号为 0
的朝代表示未知朝代。请判断并返回这排文物的所属朝代编号是否连续(如遇未知朝代可算作连续情况)。
原题:
给定一个
5
位数的数组nums
代表扑克牌中的5
张牌。其中
2~10
为数字本身,A
用1
表示,J
用11
表示,Q
用12
表示,K
用13
表示,大小王用0
表示,且大小王可以替换任意数字。要求:判断给定的
5
张牌是否是一个顺子,即是否为连续的5
个数。
示例 1:
输入: places = [0, 6, 9, 0, 7]
输出: True
示例 2:
输入: places = [7, 8, 9, 10, 11]
输出: True
提示:
places.length = 5
0 <= places[i] <= 13
解题思路
考虑不含 0
的情况下,如果 5
张数是连续的,那么这 5
个数中最大值和最小值的差为 4
。如果牌中含有 0
,那么 0
可以替代任意数字,剩下的数的最大值和最小值差应小于等于 4
。此外,剩余数不能有重复数字。基于这些考虑,可以按照以下步骤进行判断:
- 遍历
5
张牌,如果遇到0
则跳过。 - 判断
5
张牌中是否存在重复数,若存在直接返回 False,若不存在则将其加入集合。 - 计算
5
张牌的最大值和最小值。 - 最后判断最大值和最小值的差是否小于等于
4
。若成立,返回true
,否则返回false
。
复杂度分析
- 时间复杂度:
O(n)
,其中n
是字符串的长度。 - 空间复杂度:
O(k)
,其中k
是字符集的大小,通常是常数大小。
代码
/**
* @param {number[]} places
* @return {boolean}
*/
var checkDynasty = function (places) {
let max = 0;
let min = 14;
let set = new Set();
for (let i of places) {
if (i == 0) {
continue;
}
if (set.has(i)) {
return false;
} else {
set.add(i);
}
min = Math.min(min, i);
max = Math.max(max, i);
}
return max - min <= 4;
};