剑指Offer（四十五）-- 扑克牌顺子
Github仓库地址：https://github.com/Damaer/CodeSolution 笔记地址：https://damaer.github.io/CodeSolution/ 仓库介绍：刷题仓库：CodeSolution
题目描述
扑克牌可以组成顺子，大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。5张牌【A,0,3,0,5】就可以变成“1,2,3,4,5”(大小王分别看作2和4),这样就组成了顺子。（可以认为大小王是0。）
输入五张牌，如果牌能组成顺子就输出true，否则就输出false。
示例1
输入
[0,3,2,6,4]
返回值
true
思路以及解答
第一种思路，先排序，0肯定是靠左边，然后统计0的个数，后面的数，按照第一个非0的数进行递增，如果不是递增，则需要使用0牌补充，如果0牌不够，需要放回false，否则知道遍历完数组，返回true。
public boolean IsContinuous(int[] numbers) {
// 数组长度不符合直接返回
if (numbers == null || numbers.length < 5) {
return false;
}
// 先排序
Arrays.sort(numbers);
// 统计0的个数
int numOfZero = 0;
// 初始化索引
int start;
// 统计0的个数
for (start = 0; start < numbers.length; start++) {
if (numbers[start] == 0) {
numOfZero++;
} else {
// 非0的时候跳出
break;
}
}
// 暂存0的个数
int n = numOfZero;
// 当前的数值
int cur = numbers[numOfZero];
// 从0的下两个位置开始
for (start++; start < numbers.length; ) {
// 如果可变的牌数量为0
if (numOfZero == 0) {
// 和前面的一个对比
if (numbers[start] != cur + 1) {
// 不等于当前数值+1的话，直接返回false
return false;
} else {
// 当前数值+1
cur++;
}
} else {
// 不等于当前数值+1的话，直接返回false
if (numbers[start] != cur + 1) {
// 可变牌数量-1
numOfZero--;
//当前值+1
cur++;
// 遍历下一张牌
continue;
} else {
// 相等则直接将当前值+1
cur++;
}
}
// 索引滑动到下一张牌
start++;
}
return true;
}
另外一种做法，初始化一个最小牌14，最大牌0，直接使用set保存数组的元素，如果set中已经存在该元素，那么我们直接放回false，如果set中不存在该元素，则将该元素放进set中，判断该元素是否小于最小牌，小于则更新最小牌，判断该元素是否大于最大牌，如果大于最大牌，则更新当前最大牌。
import java.util.HashSet;
public class Solution45 {
public boolean IsContinuous(int [] numbers) {
if(numbers==null||numbers.length<5){
return false;
}
HashSet<Integer>set = new HashSet<>();
int min = 14;
int max = 0;
for(int i=0;i<numbers.length;i++){
if(numbers[i]!=0){
if(set.contains(numbers[i])){
return false;
}
set.add(numbers[i]);
max= Math.max(max,numbers[i]);
min = Math.min(min,numbers[i]);
}
}
return max-min<5;
}
}
借助了set，空间为5，空间复杂度是常数，可以认为是O(1)，时间复杂度也是O(1)。
【作者简介】：
秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使缓慢，驰而不息。个人写作方向：Java源码解析，JDBC，Mybatis，Spring，redis，分布式，剑指Offer，LeetCode等，认真写好每一篇文章，不喜欢标题党，不喜欢花里胡哨，大多写系列文章，不能保证我写的都完全正确，但是我保证所写的均经过实践或者查找资料。遗漏或者错误之处，还望指正。
平日时间宝贵，只能使用晚上以及周末时间学习写作 - END -
腾讯云开发者
