首页 > 试题广场 >

扑克牌顺子

[编程题]扑克牌顺子
  • 热度指数:478966 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
现在有2副扑克牌,从扑克牌中随机五张扑克牌,我们需要来判断一下是不是顺子。
有如下规则:
1. A为1,J为11,Q为12,K为13,A不能视为14
2. 大、小王为 0,0可以看作任意牌
3. 如果给出的五张牌能组成顺子(即这五张牌是连续的)就输出true,否则就输出false。
4.数据保证每组5个数字,每组最多含有4个零,数组的数取值为 [0, 13]

要求:空间复杂度 ,时间复杂度 ,本题也有时间复杂度 的解法

输入描述:
输入五张扑克牌的值


输出描述:
五张扑克牌能否组成顺子。
示例1

输入

[6,0,2,0,4]

输出

true

说明

中间的两个0一个看作3,一个看作5 。即:[6,3,2,5,4]
这样这五张牌在[2,6]区间连续,输出true 
示例2

输入

[0,3,2,6,4]

输出

true
示例3

输入

[1,0,0,1,0]

输出

false
示例4

输入

[13,12,11,0,1]

输出

false
1、排序 
2、计算所有相邻数字间隔总数 
3、计算0的个数 
4、如果2、3相等,就是顺子 
5、如果出现对子,则不是顺子
import java.util.Arrays;
public class Solution {
    public boolean IsContinuous(int[] numbers) {
        int numOfZero = 0;
        int numOfInterval = 0;
        int length = numbers.length;
        if(length == 0){
           return false;
        }
        Arrays.sort(numbers);
        for (int i = 0; i < length - 1; i++) {
            // 计算癞子数量
            if (numbers[i] == 0) {
                numOfZero++;
                continue;
            }
            // 对子,直接返回
            if (numbers[i] == numbers[i + 1]) {
                return false;
            }
            numOfInterval += numbers[i + 1] - numbers[i] - 1;
        }
        if (numOfZero >= numOfInterval) {
            return true;
        }
        return false;
    }
}

发表于 2016-08-06 16:21:14 回复(49)
L0L头像 L0L
//考略到顺子的特性,最大值和最小值之差绝对为4,
//然而又有大小王的存在,所以a[4]-a[jokers] <=4
class Solution {
public:
   bool IsContinuous( vector<int> numbers ) {
        int len=numbers.size();
        if(len!=5)	return false;
		sort(numbers.begin(),numbers.end());
		int jokers=0;//计算王的数目 
		for(int i=0;i<5&&numbers[i]==0;i++){
			jokers++;
		} 
		if(jokers>4)	return false;
	
		for(int i=jokers+1;i<5;i++){
			if(numbers[i]==numbers[i-1])//判断对子的存在 
				return false;
		}
		int dis=numbers[4]-numbers[jokers];
		if(dis<=4)	return true;
		return false;
    }
}; 

编辑于 2015-09-24 09:54:56 回复(1)
max 记录 最大值
min 记录  最小值
min ,max 都不记0
满足条件 1 max - min <5
               2 除0外没有重复的数字(牌)
               3 数组长度 为5

public boolean IsContinuous(int [] numbers) { 
int[]d = new int[14];  
d[0] = -5;  
int len = numbers.length;  
int max = -1;  
int min = 14;  
for(int i =0;i<len;i++){
    d[numbers[i]]++;  
    f(numbers[i] == 0){ 
        continue;  
    } 
    if(d[numbers[i]]>1){ 
        return false;  
    } 
    if(numbers[i] >max){
        max = numbers[i];  
    } if(numbers[i] <min){
        min = numbers[i];  
    }

} 
if(max -min<5){ 
    return true;  
} 
    return false; 
}


编辑于 2021-01-28 11:42:28 回复(79)
#python 2.7 时间:36ms 内存:5764k
# 说好的是一副牌,还会出现[3,0,0,0,0]? 出题人这么想的?
# 两个条件:1,除0外没有重复,2,max-min<5
class Solution:
    def IsContinuous(self, numbers):
        # write code here
        if len(numbers):
            while min(numbers)==0:
                numbers.remove(0)
            if max(numbers) - min(numbers)<=4 and len(numbers)==len(set(numbers)):
                return True
        return False

发表于 2017-09-10 21:24:20 回复(2)
class Solution {
public:
    bool IsContinuous( vector<int> numbers ) {
        sort(numbers.begin(), numbers.end());
        int cnt0 = 0, cntNeed = 0;
        for(int i = 0; i < 5; i++) {
            if(numbers[i] == 0) {
                ++cnt0;
            } else if(i + 1 < 5 ) {
                if(numbers[i + 1] == numbers[i]) return false;
                cntNeed += numbers[i + 1] - numbers[i] - 1;
            }
        }
        if(cntNeed > cnt0) return false;
        return true;
    }
};

发表于 2015-05-03 09:23:14 回复(7)
import java.util.HashSet;
import java.util.Set;

public class Solution {
    public boolean IsContinuous(int [] numbers) {
        if(numbers.length == 0) return false;
    	Set<Integer> set = new HashSet<>();
    	int maxn = -1, minn = 14;
    	for(int a: numbers)
    	{
    		if(!set.add(a) && a!=0) return false;
    		if(a!=0) {
    			maxn = Math.max(maxn, a);
    			minn = Math.min(minn, a);
    		}
    	}
    	if(maxn - minn <=4) return true;
    	return false;
    	
    }
}

发表于 2016-08-04 15:56:01 回复(3)

这坑爹的题目 说了5张牌 居然还给空数组 居心叵测的测试样例
排个序 计算前面0的个数zeros
然后zeros - (顺子差的数)
若zeros最后 >= 0 说明用大小王补够用 否则不行
还要判断一下只要有相同的牌直接返回false

class Solution {
public:
   bool IsContinuous(vector<int> numbers){
        if(numbers.empty()) return false;
        sort(numbers.begin(), numbers.end());
        int zeros = 0, i = 0;
        while(i < numbers.size() && numbers[i] == 0) {zeros++; i++;}
        for(i; i < numbers.size()-1; i++){
            if(numbers[i+1] == numbers[i]) return false;
            zeros -= (numbers[i+1] - numbers[i] - 1);
        }
        return zeros >= 0;        
    }
};
发表于 2018-12-26 15:02:43 回复(1)
思路:
1)没有大小王的时候即判断数是否连续;
2)有大小王的时候,判断数的间隔是否小于王的数量。小于返回true,大于返回false;
3)有相等的牌则直接返回false。
解法一;
import java.util.*;
public class Solution {
    public boolean IsContinuous(int [] numbers) {
		if(numbers == null || numbers.length <= 4)
            return false;
        
        //先排序,否则计算间隔的时候可能会出现负值,比较麻烦
        Arrays.sort(numbers);
        int totalGap = 0;
        //计算大小王的数量
        int countZero = 0;
        for(int i = 0; i < numbers.length; i++){
            if(numbers[i] == 0){
                countZero++;
                continue;
            }
            //计算两数之间的间隔
            if(i < numbers.length - 1){
                int gap = numbers[i + 1] - numbers[i] - 1;
                //如果出现对子,如2 2,则gap为-1,直接返回false
                if(gap < 0)
                    return false;
                totalGap += gap;
            }
        }
        //所有数间隔大于王数量,就返回false
        if(totalGap > countZero){
            return false;
        }
        return true;
    }
}
解法二:
import java.util.*;
public class Solution {
   public static boolean IsContinuous(int [] numbers) {
       		if(numbers == null || numbers.length <= 4)
                return false;
	        Arrays.sort(numbers);
			int count = 0;
	        for(int i : numbers){
	            if(i == 0)
	                count++;
	        }
	        //不含0,即不包含大小王
	        if(count == 0){
	            if(isSequence(numbers)){
	                return true;
	            }else{
	                return false;
	            }
	        }
	        //包含大小王
	        else{
	            if(count == 4)
	                return true;
	            int sum = 0;
	            //计算间隔数
	            for(int i = count + 1; i < numbers.length; i++){
	            	int gap = numbers[i] - numbers[i - 1] - 1;
	                if(gap < 0)
	                    return false;
	                sum += gap;
	            }
	            if(sum > count){
	                return false;
	            }
	            return true;
	        }
	    }
	    
	    private static boolean isSequence(int[] numbers){
	        
	        for(int i = 1 ; i < numbers.length; i++){
	            if(numbers[i] - numbers[i-1] != 1){
	                return false;
	            }
	        }
	        return true;
	    }
}

发表于 2017-07-22 10:16:22 回复(4)

题目描述

LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)...他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿!!“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子.....LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何, 如果牌能组成顺子就输出true,否则就输出false。为了方便起见,你可以认为大小王是0。

解题思路

要组成顺子,我们想一想最简单的情况,就是四个王再搭一个任意牌,这五张牌必然是顺子。

那么到底如何判断是不是顺子呢?

一个关键点是0的个数,就是王的个数。另一个关键点是非0元素之间的差值和。

如果这个差值的和大于王的个数,那么王是无法填补里面的间隙的,那么就形不成顺子了。

下面举个简单的例子。比如有五张牌,分别是1,3,4,5,0,那么0可以作为2,可以作为顺子,此时0 的个数是1,而间隙是(3-1-1)+(4-3-1)+(5-4-1)=1(注意,数组要先排序,所以此时数组是0,1,3,4,5),而0不要参与计算。此时0的个数为1,差值也为1,所以0可以来填补这个间隙,所以可以作为顺子。

再来看一个例子:0,0,1,5,6,0的个数为2,间隙为(5-1-1)+(6-5-1)=3,此时3>2,所以无法用0来填补,所以无法构成顺子。

最后就是注意,如果存在对子,那么肯定就不是顺子了。

分析完毕。

我的答案

import java.util.Arrays;
public class Solution {
    public boolean IsContinuous(int [] numbers) {
        if(numbers.length <= 0){
            return false;
        }

        //零的个数,即王的个数
        int zeroNum = 0;
        //排序后元素之间的差值
        int gapNum = 0;

        //数组排序
        Arrays.sort(numbers);

        //遍历数组
        for(int i=0;i<numbers.length-1;i++){
            //统计王的个数,统计到一个就重新循环,因为不需要参与后面的差值计算
            //也不需要对比是不是顺子
            if(numbers[i] == 0){
                zeroNum++;
                continue;
            }
            //不是王,并且还是对子,那肯定不是顺子了
            if(numbers[i] == numbers[i+1]){
                return false;
            }
            //不是王,计算一下两两的差值,最后与王的个数做比较
            gapNum += numbers[i+1] - numbers[i] - 1;
        }

        //差值小于王的个数,说明可以用王来构成顺子
        if(gapNum <= zeroNum){
            return true;
        }

        return false;
    }
}
编辑于 2019-03-12 12:14:47 回复(6)
Python

class Solution:
    def IsContinuous(self, numbers):
        # write code here
        if len(numbers) < 5:
            return False
        #计算0的个数
        nOfZero = numbers.count(0)
        #排序
        numbers.sort()
        #序列中间隔的值初始化为0
        sumOfGap=0
        #遍历非0部分的递增序列
        for i in range(nOfZero, len(numbers) - 1):
            small = numbers[i]
            big = numbers[i + 1]
            #当前与下一个值的比较,若相等则说明存在对子
            if small == big:
                return False
            else:
                #若不同,则得到二者的差再减1,若为0则说明连续,否则二者之间存在空缺
                sumOfGap+= (big-small - 1)
                #判断0的个数及序列中非0部分间隔值,若0不小于间隔值,则说明满足连续条件
        if nOfZero >= sumOfGap:
            return True
        else:
            return False

发表于 2017-10-17 18:01:54 回复(3)
class Solution {
public:
    bool IsContinuous( vector<int> numbers ) {
        if(numbers.size()!=5) return false;
        sort(numbers.begin(),numbers.end());
        int i=0;
        while(numbers[i]==0) i++;
        if(numbers[4]-numbers[i]>4) return false;
        for(int j=i;j<4;j++){
            if(numbers[j]==numbers[j+1]) return false;
        }
        return true;
    }
};

发表于 2017-03-15 14:01:04 回复(9)
/*
	 * 思路:大小王看为0;则牌范围为0~13;
	 * a[0]存放大小王数目; a[i] (1~13)不为0表示牌被抽到;
	 * a[i]~a[i+4] (a[i]为第一个不为0即抽到的牌);
	 * 统计满足连续其中缺少的牌 即a[i]==0的个数;
	 * 与大小王个数比较即可
	 */
public class Solution {
    public boolean IsContinuous(int [] numbers) {
    	int[] a=new int[14];
    	for(int i=0;i<numbers.length;i++){
    		a[ numbers[i] ]++;
    	}
    	
    	for(int i=1;i<a.length-6;i++){
    		if(a[i]!=0){
    			int count=0;
    			for(int j=i;j<i+5;j++){
    				if(a[j]==0){
    					count++;
    				}
    			}
    			if(count==a[0]){
    				return true;
    			}
    			break;
    		}
    	}
    	return false;   	
    }
}
编辑于 2017-02-22 19:53:47 回复(5)
import java.util.Arrays;
 public class Solution {
     public boolean IsContinuous(int [] numbers) {
         if(numbers.length != 5)    //不够5张的时候返回false;
             return false;
         Arrays.sort(numbers);    //排序,方便统计王(0)的数量以及比较是否存在相等的牌(前后比较即可)
         int res = 0;    //统计王(0)的数量
         for(int i=0;i<numbers.length;i++){
             if(numbers[i] == 0){
                 res++;
                 continue;
             }
             //王的数量小于等于3张时才需要做判断
             //判断第一张非0的牌与最后一张的差,超过4,则不可能是顺子
             //判断前后张牌是否相等,相等则不可能是顺子
             if(res !=4 && (numbers[numbers.length-1]-numbers[i]>4 ||numbers[i] == numbers[i+1]))
                 return false;
             else 
                 return true;
         }
         return true;
     }
 }
发表于 2017-10-04 16:01:42 回复(1)
sort一下,
0 的个数<5 && 正数互不相同 && 正数最大最小值相差 < 5

class Solution {
public:
    bool IsContinuous( vector<int>& a ) {
        if(a.size() != 5) return false;
        sort(a.begin(), a.end());
        int c = 0;
        while(c < 5 && a[c] == 0) ++c;
        for(int i = c; i < 5; ++i) if(i && a[i] == a[i - 1]) return false;
        return c < 5 && (a[4] - a[c]) < 5;
    }
};

发表于 2015-09-09 11:52:39 回复(0)
先排个序
遍历一遍 ,记录0的次数,后面两个数的差要是大于1就用0的个数(王的个数)替代大于1的差,不够用就false;
然后两数也不能相等
import java.util.*;
public class Solution {
    public boolean IsContinuous(int [] numbers) {
        int cnt=0;
        Arrays.sort(numbers);
        for(int i=0;i<numbers.length-1;i++){
            if(numbers[i]==0) cnt++;
            else if(numbers[i+1]-numbers[i]-1>cnt||numbers[i+1]==numbers[i]) 
                return false;
            else cnt=cnt-(numbers[i+1]-numbers[i]-1);
        }
           return true;
    }
}



发表于 2021-09-29 17:36:31 回复(0)
function IsContinuous(numbers)
{
    // write code here
    var joker = 0;
    var n = numbers.sort();
    for(let i=0;i<4;i++){
        if(n[i]==0) joker++;
        else if(n[i]==n[i+1]) return false;
    }
    return n[4]-n[joker]<5;
}

发表于 2021-08-30 21:23:41 回复(0)
class Solution:
    def IsContinuous(self, numbers):
        # write code here
        if not numbers:
            return False
        ns = [n for n in numbers if n != 0]
        return (max(ns) - min(ns) <= 4) and (len(ns) == len(set(ns)))
想法很简单:先把0拿掉,剩下的3个或4个或5个数字只要 1)不重复;2)最大最小差不超过4即可。不用关心具体有几个王。
发表于 2020-02-05 12:55:07 回复(0)
/**
@author zhengyanan
@date 2017/3/1 @time 10:54
version_2:
核心思路:
1.在verison_1的思路上进一步优化:
当从counts[i]访问到counts[i+5]时,对于访问数组边界而提前退出访问的情况,我们考虑将counts 的长度+4,,从而将这种特殊情况统一到常规情况中,从而简化处理逻辑,精简代码。

运行时间:36ms
占用内存:528k
*/
    public boolean IsContinuous(int [] numbers) {
        int[] counts = new int[18];
        for (int num:numbers)   counts[num]++;
        int left,i;
        for (left = 1; left <14; left++) {
            if (counts[left] != 0)  break;
        }
        //用left记下最小的一个非0数字
        for (i = left + 1; i <= left+4; i++) {
            if (counts[i] == 0){
                if (counts[0] == 0) return false;
                else                counts[0]--;
            }
        }
        return true;
    }
/**
@author zhengyanan
@date 2017/3/1 @time 10:25
verison-1:
核心思路:
1.先用一个长度为14的数组,记忆原始数据,下标为值,值为下标出现的次数。
2.按下标从小到大找到第一个不为0的数counts[i](一定有,因为一共5个数,撑死4个0)。
3.从counts[i]访问到counts[i+5]:
如果counts[i] == 0:就counts[0]--,(类比成拿一个0来顶);如果没有0可以用来顶,说明没法构成顺子,返回false;

如果能顺利的访问完,就说明是顺子;

如果不能访问完,就说明因为访问到了数组的边界而提前退出访问了。(比如 0,0,12,12,13) 这时我们就需要判断 已经连成的顺子的长度+counts[0]是否==5.
        如果相等,就可以把0补到最左边组成顺子,true;
        如果不等,说明有非0的对子,false;

运行时间:28ms
占用内存:503k
*/
//    public boolean IsContinuous(int [] numbers) {
//        int[] counts = new int[14];
//        for (int num:numbers)   counts[num]++;
//        int left,i;
//        for (left = 1; left <14; left++) {
//            if (counts[left] != 0)  break;
//        }
//        //用left记下最小的一个非0数字
//
//        for (i = left + 1; i <= left+4 && i<14  ; i++) {
//            if (counts[i] == 0){
//                if (counts[0] == 0) return false;
//                else                counts[0]--;
//            }
//        }
//
//        if (i == left + 5)  return true;
//        else{
//            if (14 - left + counts[0] == 5) return true;
//            else                            return false;
//        }
//    }

编辑于 2017-03-01 11:04:39 回复(1)
不用sort函数的:
class Solution {
public:
   bool IsContinuous( vector<int> numbers )
{
int len = numbers.size();
if(len == 0)
return false;
int num[14] = {0};
for(int i = 0; i<len ; i++)
{
if( numbers[i] > 0 && num[ numbers[i]] !=0 )
return false;
num[ numbers[i]]++;
}

int dif = 0;
int start = 1,end =13;
   while(num[start]!=1)
start++;
   while(num[end]!=1)
end--;
dif = end - start +1; 

return dif<=len;
    }
};
编辑于 2015-10-03 16:36:24 回复(1)
1.首先判断输入,如果为空数组或者数组的长度不到5位,则直接返回false
2.然后查看数组中是否有重复值(0除外),如果有0以外的重复值,直接返回false
3.如果没有对子,需要记录0的出现次数,同时要注意如果有4个0的话直接返回true(一定能构成顺子)
4.将数组中的0剔除,再将数组排序(从小到大),遍历排序后的值,统计需要0的个数
5.统计0的算法:相邻之间的数如果相差1,则不需要,相差2,需要一个0,相差3,需要两个0,最多相差4,需要3个0;
6.统计所有需要0的个数是否小于已有0的个数,如果小于则可以组成顺子
该题用了下Collections中的SortedSet省略了排序过程
using System.Collections.Generic;
using System.Linq;
class Solution
{
    public bool IsContinuous(int[] numbers)
    {
        if(null == numbers || numbers.Length <= 4) return false;
        // write code here
        List<int> list = new List<int>(numbers);
            SortedSet<int> set = new SortedSet<int>();
            int countZero = 0;
            bool flag = false;
            foreach (var item in list)
            {
                flag = set.Add(item);
                if (flag && item == 0)
                {
                    //第一次加入大小王
                    countZero = 1;
                }
                //判断是否有对子
                else if (!flag)
                {
                    //表示不是第一次加入大小王
                    if (item == 0)
                    {
                        countZero++;
                    }
                    else
                    {
                        //有对子,不能成为顺子
                        return false;
                    }
                }
            }
            //没有大小王
            if (countZero == 0)
            {
                for (int i = 0; i <= set.Count - 2; i++)
                {
                    if (set.ElementAt(i + 1) - set.ElementAt(i) > 1)
                    {
                        return false;
                    }
                }
                return true;
            }
            //有大小王
            //有4个大小王
            if (set.Count == 1) return true;

            //记录需要大小王的个数
            int countSub = 0;
            set.Remove(0);
            for (int i = 0; i <= set.Count - 2; i++)
            {
                countSub += (set.ElementAt(i+1) - set.ElementAt(i) - 1);
            }
            if (countZero >= countSub) return true;

            return false;
    }
}



发表于 2019-12-03 16:36:15 回复(0)