剑指：扑克牌的顺子

题目描述

从扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。

2～10 为数字本身，A 为1，J 为 11，Q 为 12，K 为 13，大小王可以看做任意数字。

为了方便，大小王均以 0 来表示，并且假设这副牌中大小王均有两张。

样例1

输入：[8,9,10,11,12]

输出：true

样例2

输入：[0,8,9,11,12]

输出：true

解法一

• 对数组排序；
• 计算出 0 的个数 zeroCount；
• 从第一个不是 0 的数字开始遍历，与后一个数字比较，如果相等，直接返回 false；否则累计 gap；
• 判断 zeroCount 是否大于等于 gap。

import java.util.Arrays;

class Solution {

    /**
     * 判断是否是连续的数字
     *
     * @param numbers 数组
     * @return 是否是顺子
     */
    public boolean isContinuous(int [] numbers) {
        if (numbers == null || numbers.length == 0) {
            return false;
        }
        int zeroCount = 0;
        Arrays.sort(numbers);
        for (int e : numbers) {
            if (e > 0) {
                break;
            }
            ++zeroCount;
        }

        int p = zeroCount, q = p + 1, n = numbers.length;
        int gap = 0;
        while (q < n) {
            if (numbers[p] == numbers[q]) {
                return false;
            }
            gap += (numbers[q] - numbers[p] - 1);
            p = q;
            ++q;
        }
        return gap <= zeroCount;

    }
}

解二：

必须满足两个条件

1. 除0外没有重复的数

2. max - min < 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;
}

或

public class Solution {
    public boolean isContinuous(int [] numbers) {
        if(numbers.length != 5) return false;
        int min = 14;
        int max = -1;
        int flag = 0;
        for(int i = 0; i < numbers.length; i++) {
            int number = numbers[i];
            if(number < 0 || number > 13) return false;
            if(number == 0) continue;
            if(((flag >> number) & 1) == 1) return false;
            flag |= (1 << number);
            if(number > max) max = number;
            if(number < min) min = number;
            if(max - min >= 5) return false;
        }
        return true;
    }
}

先是用的数组做的标记，改成了用bit做标记，节省空间，效率也应该高一些