AlgoPressAppearance
61-扑克牌中的顺子
题目描述
https://leetcode.cn/problems/bu-ke-pai-zhong-de-shun-zi-lcof
从若干副扑克牌中随机抽 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] .
思路分析
基本思路 ：排序，找出 0 的个数，后面继续计算的相隔的数字，如果小于count+1，则count递减，如果大于count+1说明超过了，无法作为顺子
实现代码
csharp
public class Solution {
public bool IsStraight(int[] nums) {
if(nums == null || nums.Length != 5){
return false;
}
//根据0的个数，分三种情况 0 个 ， 1个, 2个 ：不能假设大王只有两个
//冒泡排序
for(int i=0; i < nums.Length -1; i++){
for(int j=i+1; j < nums.Length; j++){
if(nums[i] > nums[j]){
//swap
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
}
// 出现了3个大王 , [ 11, 0, 9, 0, 0 ] ？ 一副扑克牌有三大小王？ 我傻了
// 不能蛮干
// 求出0的数量 计算为 count ， 后面每次计算两张牌的 GAP 如果大于 count 则失败, 如果小于等于 count , 则 count 减掉对应数值，继续操作
int count = 0;
for(int i = 0; i<nums.Length-1; i++){
if(nums[i] == 0){
count ++;
}
else if(nums[i+1] - nums[i] == 1){
//继续
}
else if(nums[i+1] - nums[i] > 1){
count -= nums[i+1] - nums[i] - 1;
if(count < 0){
return false;
}
}
else{ //两张牌相等，也退出
return false;
}
}
return true;
}
}
思路2：最大牌和最小牌
找出牌中的最大牌和最小牌，他们相减小于5即为顺子，遍历中跳过0，同时注意出现了不能出现相同的牌。
实现代码
csharp
public class Solution {
public bool IsStraight(int[] nums) {
int min = 14;
int max = 0;
Dictionary<int,int> dict = new Dictionary<int,int>();
for(int i=0; i<nums.Length; i++){
if(nums[i] == 0){
continue;
}
min = Math.Min(min,nums[i]);
max = Math.Max(max,nums[i]);
if(dict.ContainsKey(nums[i])){
return false;
}
dict.Add(nums[i],nums[i]);
}
return max - min < 5;
}
}
复习:20220610
csharp
public class Solution {
public bool IsStraight(int[] nums) {
HashSet<int> set = new HashSet<int>();
int min = int.MaxValue;
int max = int.MinValue;
for(int i=0; i<nums.Length; i++){
if(nums[i] != 0){
if(set.Contains(nums[i])){
return false;
}
set.Add(nums[i]);
min = Math.Min(min,nums[i]);
max = Math.Max(max,nums[i]);
}
}
return max - min < 5;
}
}