题目:
从扑克牌种随机抽5张牌,判断是不是一个顺子,即是否连续。2~10为数字本身,A为1,J为11,Q为12,K为13,而大小王可以表示任意数字。(大小王可以超过2个)
解法1:
首先是将大小王表示任意数字(可能有多个大小王),等价成0可以表示任意数字。也就是{0,2,3,5,6}会被看成是顺子。那么思路如下:
1.对抽到的5张牌进行排序;
2.找出0的个数;
3.算出相邻数字的空缺总数;比如3和5之间相差2,必须要有1个0才行。相差3就得要有两个0
4.如果0的个数大于等于空缺总数,说明连续,反之不连续;
5.需要判断相邻数字是否相等,如果有出现相等,说明不是顺子。
调用了系统的排序算法。排序不是本题的考察点,所以重点关注后面怎么实现。
import java.util.Arrays;
public class Solution {
public boolean isContinuous(int [] numbers) {
if(numbers==null || numbers.length<=0)
return false;
Arrays.sort(numbers);//调用库完成排序(快排)
int count = 0;//记录0的个数
int numberOfGap = 0;//记录不连续的次数
for(int i=0;i<numbers.length;i++){//统计0的个数
if(numbers[i]==0)
count++;
}
int small = count;//记录数组中第一个非0数的索引
while(small < numbers.length-1){
if(numbers[small]==numbers[small+1])//不能相等
return false;
//需要判断间断的情况。对应步骤3和4,因为已经排过序,所以这里不用判断大小
int c = numbers[small+1] - numbers[small]-1;//要减1!
numberOfGap += c;//其实可以不用c,两句合并一句
small++;
}
if(count >= numberOfGap) //大于等于都行
return true;
return false;
}
}解法2:
有大佬使用TreeSet集合,很有意思,值得学习一下。不管是用什么数据结构,总是需要进行排序,连续的两张牌不能相同,也可以选择去重的数据结构。因此数据结构的选择不唯一。
以TreeSet为例,0不用装进去,但是要统计0的次数count,在装给集合任意5个数的时候,集合的size肯定小于等于5。如果size+count等于5,说明此时要判断间断情况,看赖子是否能成功拼成顺子。如果size+count不等于5([1,0,0,1,0]这种情况,count是3,size是1),其实也可以说是size+count小于5的情况,因为不可能出现大于5(当时给TreeSet装元素的时候,一共就只准备了5个元素),这种情况下,就是出现了重复元素,因此是false。
最巧的点在于,只需要判断TreeSet的最小和最大元素差值小于5,就可以连成顺子。因为集合中是非0的数字,如果差距太大,0的数量弥补不了差距,就形成不了顺子,所以这个判断是真的妙。
import java.util.TreeSet;
public class Solution {
public boolean isContinuous(int [] n) {
if (n.length < 5 || n.length > 5) {
return false;
}
int num = 0;//记录0的个数
TreeSet<Integer> set = new TreeSet<> ();
for (int i=0; i<n.length;i++) {//一共只装5个数
if (n[i]==0) {
num ++;
} else {
set.add(n[i]);
}
}
if ((num + set.size()) < 5) //这里也可以写 !5。
return false;
if ((set.last() - set.first()) < 5) //首尾相差的值必须小于5
return true;
return false;
}
}写法3:
解法2的最大最小相差不到5这一思想,对于解法1也是有效的,只不过解法1判断重复数字步骤不能去掉(解法2利用TreeSet完成了去重)。将解法1改动后,写法如下
import java.util.Arrays;
public class Solution {
public boolean isContinuous(int [] numbers) {
if(numbers==null || numbers.length<=0)
return false;
Arrays.sort(numbers);//调用库完成排序(快排)
int count = 0;//记录0的个数
int numberOfGap = 0;//记录不连续的次数
for(int i=0;i<numbers.length;i++){//统计0的个数
if(numbers[i]==0)
count++;
}
int small = count;//记录数组中第一个非0数的角标索引(要记录不连续)
while(small < numbers.length-1){
if(numbers[small]==numbers[small+1])//判断相邻两数是否相等
return false;
small++;
}
if((numbers[numbers.length-1] - numbers[count]) <5)
return true;
return false;
}
}


京公网安备 11010502036488号