题目:
从扑克牌种随机抽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; } }