1. 首页
  2. 剑指offer经典面试题

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

[剑指 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/


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

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

链接:https://www.javajike.com/article/3301.html

« [剑指 Offer 第 2 版第 56 题] “数字在排序数组中出现的次数”做题记录
[剑指 Offer 第 2 版第 62 题] “孩子们的游戏(圆圈中最后剩下的数)”做题记录»

相关推荐

QR code