题目
- 从若干副扑克牌中随机抽
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
代码
- 集合 Set + 遍历
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; // 若有重复,提前返回 false
repeat.add(num); // 添加此牌至 Set
}
return max - min < 5; // 最大牌 - 最小牌 < 5 则可构成顺子
}
}
代码分析
:题解 from
1、此 5 张牌是顺子的 充分条件
如下:
除大小王外,所有牌 无重复 ;
设此 55 张牌中最大的牌为 max ,最小的牌为 min (大小王除外),则需满足:max - min < 5
- 排序 + 遍历
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 则可构成顺子
}
}
代码分析
:
1、先对数组执行排序。
2、判别重复: 排序数组中的相同元素位置相邻,因此可通过遍历数组,判断 nums[i] = nums[i + 1]
是否成立来判重。
3、获取最大
/ 最小
的牌: 排序后,数组末位元素 nums[4] 为最大牌;元素 nums[joker] 为最小牌,其中 joker 为大小王的数量。
- $O(n)$
class Solution {
public:
bool isContinuous( vector<int> nums) {
if(!nums.size()) return false;
int ma = 0, mi = INT_MAX;
unordered_map<int,int> map;
for(auto a : nums){
if(a){
ma = max(ma, a);
mi = min(mi, a);
}
map[a]++;
}
int exist = 0;
for(int i = mi + 1; i < ma; i++)
if(map[i]) exist++;
if(map[0] + ma - mi - 1 + exist < 5) return false;
return ma - mi - 1 <= map[0] + exist;
}
};
代码分析
:代码写的有点多,但复杂度还行 AcWing题目
- 改良版
class Solution {
public:
// 排序,删 0
// 判重,有重复的就一定不是顺子
// 最大值 - 最小值 是否 < 5
bool isContinuous( vector<int> nums) {
if(!nums.size()) return false;
int l = 0, r = nums.size() - 1;
sort(nums.begin(), nums.end());
while(!nums[l]) l++;
for(int i = l + 1; i < r; i++){
if(nums[i-1] == nums[i])
return false;
}
return nums[r] - nums[l] < 5;
}
};
本文题目
:扑克牌中的顺子