[剑指 Offer 第 2 版第 61 题] “n 个骰子的点数”做题记录

第 61 题：扑克牌顺子（掌握位运算占位的技巧）

传送门：扑克牌的顺子。

从扑克牌中随机抽 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

思路：基本思路就是把不符合题目要求的情况全部排除掉，剩下的就是正确的了。

python 代码：

  class Solution(object):
        def isContinuous(self, numbers):
            """
            :type numbers: List[int]
            :rtype: bool
            """
            size = len(numbers)
            if size != 5:
                return False
            # 最小值和最大值都设置成一个不可能取到的值
            min_val = 14
            max_val = -1

            flag = 0
            for num in numbers:
                if not 0 <= num <= 13:
                    return False
                if num == 0:
                    continue
                # 右移：看看这一位是不是用过了
                if (flag >> num) & 1 == 1:
                    return False

                # 左移：表示这一位我现在要占用
                flag = flag | (1 << num)

                min_val = min(min_val, num)
                max_val = max(max_val, num)
                if max_val - min_val >= 5:
                    return False
            return True

Python 代码：

  class Solution:
        def IsContinuous(self, numbers):
            # write code here
            if len(numbers) < 5:
                return False
            max_num = -1
            min_num = 14
            flag = 0
            for number in numbers:
                if number < 0 or number > 13:
                    return False
                if number == 0:
                    continue
                if (flag >> number) & 1 == 1:
                    return False
                flag |= 1 << number
                if number < min_num:
                    min_num = number
                if number > max_num:
                    max_num = number
                if max_num - min_num >= 5:
                    return False
            return True

Java 代码：

  import java.util.Arrays;

    public class Solution {

        public boolean isContinuous(int[] numbers) {
            int len = numbers.length;
            if (len != 5) {
                return false;
            }
            Arrays.sort(numbers);
            // "0" 的个数
            int zeroCount = 0;
            // 当前数与后一个数的距离，距离为 1，表示是顺子
            int diffDistance = 0;
            for (int i = 0; i < 4; i++) {
                if (numbers[i] == 0) {
                    zeroCount++;
                    continue;
                }
                if (numbers[i] == numbers[i + 1]) {
                    return false;
                } else {
                    diffDistance += (numbers[i + 1] - numbers[i] - 1);
                }

            }
            return zeroCount >= diffDistance;
        }
    }

Java 代码：

  private boolean isOrderly(int[] number) {
        //1、非空判断
        if (number == null){
            return false;
        }

        //2、计算 0 的个数
        int zero = 0;
        for (int num : number) {
            if (num == 0) {
                zero++;
            }
        }

        //3、将数组排序
        Arrays.sort(number);

        //4、排序完成之后 从非零数据进行两两判断
        int small = zero;
        int big = small + 1;
        int numberGap = 0;

        //5、排除一种情况  相邻数据不相等情况
        //进行循环的基础条件
        while (big < number.length) {
            if (number[small] == number[big]) {
                return false;//有对子的存在
            }
            //统计相邻之间的空格
            numberGap += number[big] - number[small] - 1;
            //所有的数据进行后移一位
            small = big;
            big++;
        }
        //判断所有的间隔与0的个数 小于或者等于则是有序的 否则则是无序的
        return numberGap <= zero;
    }

Java 代码：

  import java.util.Arrays;

    public class Solution {

        public boolean isContinuous(int[] numbers) {
            int len = numbers.length;
            if (len != 5) {
                return false;
            }
            Arrays.sort(numbers);
            // "0" 的个数
            int zeroCount = 0;
            // 当前数与后一个数的距离，距离为 1，表示是顺子
            int diffDistance = 0;
            for (int i = 0; i < 4; i++) {
                if (numbers[i] == 0) {
                    zeroCount++;
                    continue;
                }
                if (numbers[i] == numbers[i + 1]) {
                    return false;
                } else {
                    diffDistance += (numbers[i + 1] - numbers[i] - 1);
                }

            }
            return zeroCount >= diffDistance;
        }
    }

作者：liweiwei1419

来源：https://liweiwei1419.github.io/sword-for-offer/