首页 > 试题广场 >

扑克牌顺子

[编程题]扑克牌顺子

热度指数：484102 时间限制：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]

要求：空间复杂度 $O(1)$ ，时间复杂度 $O(nlogn)$ ，本题也有时间复杂度 $O(n)$ 的解法

输入描述:

输入五张扑克牌的值

输出描述:

五张扑克牌能否组成顺子。

示例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

算法知识视频讲解

Java

୧⍢⃝୨

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param numbers int整型一维数组
     * @return bool布尔型
     */
    public boolean IsContinuous (int[] numbers) {
        Arrays.sort(numbers);
        int count0 = numbers[0] == 0 ? 1 : 0;
        int gap = 0;
        for (int i = 1; i < numbers.length; i++) {
            if (numbers[i] == 0) {
                count0++;
            } else if (numbers[i - 1] != 0) {
                if(numbers[i] == numbers[i-1]){
                    return false;
                }
                gap += numbers[i] - numbers[i - 1] - 1;
            }
        }

        return count0 - gap >= 0 ? true : false;
    }

}

发表于 2024-08-09 15:37:24 回复(0)

Java

牛客839384289号

public boolean IsContinuous (int[] numbers) {
    // write code here
    Arrays.sort(numbers);
    int diff=0 ,zeroNum=0;
    for(int i=0;i<numbers.length;i++){
        if(numbers[i]==0){
            zeroNum++;
        }else if(i>0 && numbers[i-1]!=0){
            if(numbers[i]!=numbers[i-1]){
                diff+=(numbers[i]-numbers[i-1])-1;
            }else{
                return false;
            }
        }
    }
    return diff<=zeroNum;
}

编辑于 2024-03-17 15:41:06 回复(0)

Java

彼岸花开不见叶

1.除了0以外的数字重复就不能组成顺子

2.最大值和最小值差距超过4就能组成顺子

    public boolean IsContinuous (int[] numbers) {
        // write code here
        int min = 14, max = 0;
        for (int i = 0; i < numbers.length; i++) {
            //判重，除了0以外的数字不能重复
            if ((numbers[i] == min || numbers[i] == max) && numbers[i] != 0) {
                return false;
            }
            //记录最小值，最小值不能为0
            if (numbers[i] < min && numbers[i] != 0) {
                min = numbers[i];
            }
            //记录最大值
            if (numbers[i] > max) {
                max = numbers[i];
            }
            //最大值和最小值超过4就不可能构成顺子
            if (max - min > 4) {
                return false;
            }
        }
        return true;
    }

发表于 2023-09-26 23:40:48 回复(0)

Java

SUMMERENT

import java.util.*;

public class Solution {
    public boolean IsContinuous(int [] numbers) {
        //先排序
        Arrays.sort(numbers);
        int count = 0;
        for (int num : numbers) {
            if (num == 0) {
                count++;
            }
        }
        //新数组不带0的
        int[] c = Arrays.copyOfRange(numbers,count,numbers.length);
        boolean flag = false;
        int sum = 0;
        for (int i = 0; i < c.length-1; i++) {
            if( c[i] == c[i+1]){
                return flag;
            } else if (c[i] != c[i+1] && c[i+1]-c[i] != 1) {
                sum += c[i+1]-c[i]-1;
            }
        }
        if (sum <= count){
            flag = true;
        }
        return flag;
    }
}

发表于 2023-06-15 13:54:05 回复(0)

Java

master_yy

public boolean IsContinuous(int[] numbers) {
        int max = 0;
        int min = 14;
        for(int i = 0; i < numbers.length; i++) {
            // 如果有重复值, 并且重复值不为 0, 返回 false
            if((numbers[i] == min || numbers[i] == max) && numbers[i] != 0) {
                return false;
            }
            if(max - min > 4) {
                return false;
            }
            // 更新最大值
            if(max < numbers[i]) {
                max = numbers[i];
            }
            // 更新最小值, 遇到 0 不更新
            if(min > numbers[i] && numbers[i] != 0) {
                min = numbers[i];
            }
        }
        // 最后一次更新最大值, 最小值, 还没有进行判断
        return max - min <= 4;
    }

发表于 2022-12-15 22:04:04 回复(0)

Java

zhaoxfan

import java.util.Arrays;
public class Solution {
    public boolean IsContinuous(int [] numbers) {
        int count=0;
        Arrays.sort(numbers);
        for(int i=0; i<4; i++) {
            if(numbers[i] == 0) count++;
            else if(numbers[i] == numbers[i+1]) return false;
        }
        return numbers[4]-numbers[count]<5;
    }
}

发表于 2022-08-01 22:31:31 回复(0)

Java

勇敢牛牛不怕难

发表于 2022-08-01 17:11:03 回复(0)

Java

刷题快乐一生

要求：空间复杂度 O(1)O(1)，时间复杂度 O(nlogn)O(nlogn)，本题也有时间复杂度 O(n)的解法

这就是我疑惑的关键，如果不牺牲空间，你怎么在空间复杂度为O(1)的情况下让时间复杂度为O(n)？

所以我说一下我的想法，这里其实就是我认为最大的区别就是去重的问题

方法一：因为空间复杂度为O(1)，所以不能创建新的容器。所以只能通过排序去去重

public class 扑克牌顺子 {
    public boolean IsContinuous(int [] numbers) {
        if(numbers.length < 5) return false;
        //先排序
        Arrays.sort(numbers);
        int king = 0;
        int max = 0;
        int min = 14;
        for (int i = 0; i < numbers.length; i++) {
            //如果是0直接跳过
            if(numbers[i] == 0){
                king++;
                continue;
            }
            //排除有重复的情况
            if(i + 1 < numbers.length && numbers[i] == numbers[i +1 ]) return false;
            //用最大值和最小值卡区间
            if(numbers[i] < min) min = numbers[i];
            if(numbers[i] > max) max = numbers[i];
        }
        //如果0在最大值和最小值的区间，比如  2  1  0  0  5，差值就是4，直接返回
        if(max - min == 4) return true;
        //如果0不在区间，比如 0  1  0  2  3.那么最大值和最小值的差值一定等于数组长度减去0的个数 - 1
        if(max - min == numbers.length - king - 1) return true;
        return false;
    }
}

方法二：这种的话就是时间复杂度是O(n)，典型的牺牲空间换效率，和我上面的代码没啥不一样，就是没有了排序，用Set代替了去重的功能

public class 扑克牌顺子_新容器 {
    public boolean IsContinuous(int [] numbers) {
        if(numbers.length < 5) return false;
        Set<Integer> set = new HashSet<>();
        int king = 0;
        int max = 0;
        int min = 14;
        for (int i = 0; i < numbers.length; i++) {
            //如果是0直接跳过
            if(numbers[i] == 0){
                king++;
                continue;
            }
            //排除有重复的情况
            if(set.contains(numbers[i])) return false;
            else set.add(numbers[i]);
            //用最大值和最小值卡区间
            if(numbers[i] < min) min = numbers[i];
            if(numbers[i] > max) max = numbers[i];
        }
        //如果0在最大值和最小值的区间，比如  2  1  0  0  5，差值就是4，直接返回
        if(max - min == 4) return true;
        //如果0不在区间，比如 0  1  0  2  3.那么最大值和最小值的差值一定等于数组长度减去0的个数 - 1
        if(max - min == numbers.length - king - 1) return true;
        return false;
    }
}

发表于 2022-07-17 11:24:21 回复(0)

Java

牛客990155861号

public class Solution {
    public boolean IsContinuous(int [] numbers) {
        int len = 5;
        int min = 14;
        int max = 0;
        int count = 0;
        int n = 0;
        for(int i: numbers){
            if(i == 0){
                count++;
            } else {
                min = i<min?i:min;
                max = i>max?i:max;
            }
        }
        
        if( max - min > len - 1 || count == len ){
            return false;
        }
        
        for(int i = 0 ; i < numbers.length; i++){
            if(numbers[i] > 0){
                n += (numbers[i] == 1 ? 1 : 0);
                numbers[i] = numbers[i] - min;
            }
        }
        
        if(n > 1){
            return false;
        }
        
        int t;
        for(int i = 0 ; i < numbers.length; ){
            if (numbers[i] == 0 || numbers[i] == i){
                i++;
                continue;
            }
            if( numbers[numbers[i]]  == numbers[i] ){
                return false;
            } else {
                t = numbers[numbers[i]];
                numbers[numbers[i]] = numbers[i];
                numbers[i] = t;
            }
        }
        
        return true;
    }
}

3次遍历 + 5个变量

发表于 2022-06-19 21:32:40 回复(0)

Java

AgathaSeraphery

import java.util.*;
/**
1.先对数组排序
2.遍历数组，找出其中0的个数，同时判断有没有非0且重复的牌，
  如果有那么返回false
3.确定数组中的非0牌不重复后，找出非0牌的最大值和最小值left、right
4.从left到right要保持连续，需要right-left+1张牌，
    若整个数组的长度大于等于right-left+1，则肯定可以构成顺子，返回true
    否则返回false

*/
public class Solution {
    public boolean IsContinuous(int [] numbers) {
        Arrays.sort(numbers);
        int count = 0;
        for(int  i = 0;i <numbers.length;++i){ 
            if(numbers[i] != 0){
                count = i;
                for(; i <numbers.length-1;++i){
                    if(numbers[i] == numbers[i+1])
                        return false;
                }
                break;
            }
        }
        
        int left = numbers[count];
        int right = numbers[numbers.length-1];
        if(right - left +1 <= numbers.length){
            return true;
        }else{
            return false;
        }

    }
}

发表于 2022-06-18 23:25:24 回复(0)

Java

NorthXwind

import java.util.*;

public class Solution {
    public boolean IsContinuous(int [] numbers) {
        Arrays.sort(numbers);
        int zero = 0;
        int gap = 0;
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] == 0) {
                zero++;
            } else {
                if (i > 0 && numbers[i - 1] != 0 ) {
                    if (numbers[i] == numbers[i - 1]) {
                        return false;
                    } else {
                        gap += numbers[i] - numbers[i - 1] - 1;
                    }

                }
            }
        }
        if (gap <= zero) {
            return true;
        } else {
            return false;
        }




    }
}

发表于 2022-06-18 15:01:03 回复(0)

Java

只会暴力做题

遍历一次，维护0出现的次数和牌组中的最大值、最小值，通过最大值和最小值计算中牌组组成顺子需要的0的数量与实际0的数量比较得出结果，遍历时还需要维护一个set判断是否有相同数出现

import java.util.*;
public class Solution {
    public boolean IsContinuous(int[] numbers) {
        if (numbers == null || numbers.length == 0) {
            return false;
        }
        int maxNum = 0;
        int minNum = 14;
        int count0 = 0;
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < 5; i++) {
            if (numbers[i] == 0) {
                count0++;
            } else {
                if (!set.add(numbers[i])) {
                    return false;
                }
                maxNum = Math.max(maxNum, numbers[i]);
                minNum = Math.min(minNum, numbers[i]);
            }
        }
        int need0 = maxNum - minNum + count0 - 4;
        return count0 >= need0;
    }
}

发表于 2022-05-27 20:45:05 回复(0)

Java

blue&&lan

这么简单都要想半天。。。

import java.util.*;
public class Solution {
    public boolean IsContinuous(int [] numbers) {
        int max = 0;
        int min = Integer.MAX_VALUE;
        int j = 0;
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < 5; i++) {
            max = numbers[i] > max ? numbers[i] : max;
            if (numbers[i] != 0)min = numbers[i] < min ? numbers[i] : min;
            if (numbers[i] != 0)set.add(numbers[i]);
            if (numbers[i] == 0)j++;
        }
        if (set.size() + j == 5) {
            if (max - min <= 4) {
                return true;
            }
        }
        return false;
    }
}

发表于 2022-05-06 13:07:53 回复(0)

Java

牛客112285422号

import java.util.*;

public class Solution {
public boolean IsContinuous(int [] numbers) {
//排序
Arrays.sort(numbers);
//判断是否有相同的
for (int i=4;i>0;i--){
if (numbers[i]==numbers[i-1]&&numbers[i]!=0)
return false;
}

//遇到0，temp-1，相当于可以顶替一个缺失数字
int temp=0;
for (int i=3;i>=0;i--){
if (numbers[i]==0)
temp-=1;
else
temp=temp+numbers[i+1]-numbers[i]-1;
}
return temp<=0?true:false;
}
}

发表于 2022-03-21 23:59:24 回复(0)

Java

苏沐枫

O(N)复杂度
1、进行牌值与数量的映射，用数组即可
2、统计0数量，方便后续填充
3、找到数字值最小的牌
4、从该牌位置向后搜索，遇到元素值重复就返回false，遇到数量为0则用0填充（如果还有0）
5、双指针找到最大和最小的牌
6、最大牌减最小牌加0数量-1得等于5

public class Solution {
    public boolean IsContinuous(int [] numbers) {
        int[] indexs = new int[14];
        for(int i=0; i<numbers.length; i++) {
            indexs[numbers[i]]++;
        }
        //统计0数量
        int zeroCount = indexs[0];
        int index = 1;
        //找到第一个数字位置
        while(indexs[index]==0) {
                index++;
            }
        //模拟放置空白位置
        for(; index<14; index++) {
            if(indexs[index]>1)
                return false;
            if(indexs[index]<1) {
                if(zeroCount>0) {
                    indexs[index] = 1;
                    zeroCount--;
                }

            }

        }
        //双指针找到两端
        int i=1;
        for(;i<14;i++) {
            if(indexs[i]==1)
                break;
        }
        int j = 13;
        for(;j>=0; j--) {
            if(indexs[j]==1)
                break;
        }
        return j-i+zeroCount+1 == 5;
    }
}

发表于 2022-03-06 11:13:42 回复(0)

Java

牛客989812257号

import java.lang.Math;
import java.util.HashSet;
public class Solution {
   
    public boolean IsContinuous(int [] numbers) {
        HashSet<Integer> set = new HashSet();
        int max = -1;
        int min = 14;
        for(int i=0;i<numbers.length;i++){
            if(numbers[i]==0){
                continue;
            }
            if(set.contains(numbers[i])){
                return false;
            }
            set.add(numbers[i]);
            max = Math.max(max,numbers[i]);
            min = Math.min(min,numbers[i]);
            if(max-min>=5){
                return false;
            }
        }
        return true;
    }
}

发表于 2022-02-20 15:34:36 回复(1)

Java

菲尼克斯弗兰克

import java.util.*;

public class Solution {
    public boolean IsContinuous(int [] numbers) {
        Arrays.sort(numbers); // 先排序
        int cnt = 0, dif = 0;
        for (int i = 0; i < numbers.length-1; i++) {
            if (numbers[i] == 0) cnt++;
            else {
                // 站位相同非0 直接返回
                if (numbers[i] == numbers[i+1]) return false;
                dif += numbers[i+1] - numbers[i] - 1;
            }
        }
        return dif <= cnt; // 0够用补齐空缺位置就行
    }
}

发表于 2022-01-22 11:35:43 回复(0)

Java

浮鸟(BAT实习ing，目标外企~)

解法1：

import java.util.*;
public class Solution {
    public boolean IsContinuous(int [] numbers) {
        // 解法1：直接排序以后，根据条件判断
        Arrays.sort(numbers);
        // 遍历排序后数组，顺便统计0的个数（定位除0外最小元素）
        int kings=0;
        for(int i=0;i<=3;i++){
            // 记录0的个数
            if(numbers[i]==0){
                kings++;
            }
            // 一旦遇到除0以外的相等值，返回false
            else if(numbers[i]==numbers[i+1]){
                return false;
            }
        }
        // 最终的判定条件为：如果最大值-除0以外的最小值<5,算顺子
        return numbers[4]-numbers[kings]<5;
    }
}

解法2：

import java.util.*;
public class Solution {
    public boolean IsContinuous(int [] numbers) {
        // 解法2：依赖set
        Set<Integer> set = new HashSet<>();
        int max=Integer.MIN_VALUE;
        int min=Integer.MAX_VALUE;
        
        for(int n : numbers){
            // 如果n为0，跳过(不靠0来定位，0也就没用了)
            if(n==0)
                continue;
            // 如果包含相同元素，返回false
            if(set.contains(n))
                return false;
            // set记录n
            set.add(n);
            // 更新最大值最小值
            max = Math.max(max,n);
            min = Math.min(min,n);
        }
        // 最终的判定条件为：如果最大值-除0以外的最小值<5,算顺子
        return max-min<5;
    }
}

发表于 2022-01-19 23:54:00 回复(0)

提交观点

问题信息

模拟

难度：

236条回答 1329收藏 121755浏览

通过挑战的用户

查看代码

Flawles...

2022-09-16 12:21:38
牛客73585...

2022-09-16 12:05:53
Tommyle...

2022-09-16 11:12:01
远方不姓方

2022-09-16 10:50:02
牛客71137...

2022-09-16 09:03:59

扑克牌顺子

输入描述:

输出描述:

输入

输出

说明

输入

输出

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题