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 -