剑指 Offer - 45 - 扑克牌顺子

Question

题目

从扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这 5 张牌是不是连续的。2~10 为数字本身，A 为 1，J 为 11，Q 为 12，K 为 13，而大、小王可以看成任意数字。

如果牌能组成顺子就输出 true，否则就输出 false。为了方便起见，你可以认为大小王是 0。

解析

两种思路。

1、思路一

先把数组排序。

由于 0 可以当成任意数字，我们可以用 0 去补满数组中的空缺。如果排序之后的数组不是连续的，即相邻的两个数字相隔若干个数字，但只要我们有足够的 0 可以补满这两个数字的空缺，这个数组实际上还是连续的。

举个例子，数组排序之后为 {0，1，3，4，5} ，在 1 和 3 之间空缺了一个 2，刚好我们有一个 0，也就是我们可以把它当成 2 去填补这个空缺 。

分析了上面的问题之后，我们就可以整理出解题步骤:

• 首先把数组排序，再统计数组中 0 的个数，最后统计排序之后的数组中相邻数字之间的空缺总数；
• 如果空缺的总数小于或者等于 0 的个数，那么这个数组就是连续的，反之则不连续；
• 还需要注意: 如果数组中的非 0 数字重复出现，则该数组不是连续的。即如果一副牌里含有对子，则不可能是顺子；

代码:

import java.util.Arrays;
public class Solution {
    public boolean isContinuous(int[] numbers) {
        if (numbers.length != 5)
            return false;
        Arrays.sort(numbers);
        int interval = 0, zero = 0;
        for (int i = 0; i < 4; i++) {
            if (numbers[i] == 0) {//写在循环前面, 且 numbers[4]不需要判断了
                zero++;
                continue;// 记得不要判断下面的对子了，因为 number[i+1]有可能也是 0
            }
            if (numbers[i] == numbers[i + 1])
                return false;
            interval += numbers[i + 1] - numbers[i] - 1;
        }
        return zero >= interval;
    }
}

2、思路二

思路二的判断点:

• 最大的牌到最小的牌的距离要小于 5 。
• 也是不能有重复的牌 (除 0 外)；

因为我们没有对数组排序，这里用位操作来判断数组中是否含有重复的数字。

public class Solution {
    public boolean isContinuous(int[] numbers) {
        if (numbers.length != 5)
            return false;
        int max = -1, min = 14;
        int bit = 0; // 用 bit 判断是否相同
        for (int num : numbers) {
            if (num > 13 || num < 0) return false;
            if (num == 0) continue;
            if (((bit >> num) & 1) != 0) return false;
            bit |= (1 << num);
            if(num > max) max = num;
            if(num < min) min = num;
            if(max - min >= 5) return false;
        }
        return true;
    }
}