剑指offer题解汇总 Java实现

https://blog.csdn.net/guliguliguliguli/article/details/126089434

本题链接

知识分类篇 - 模拟 - JZ61 扑克牌顺子

题目

题目主要信息

• 两副扑克牌抽五张，判断是否为顺子
• A为1，J为11，Q为12，K为13
• 大、小王为0，0可以看作任意牌

方案一 哈希表

哈希表

哈希表是一种根据关键码（key）直接访问值（value）的一种数据结构，而这种直接访问意味着只要直到key就能在 O(1) 时间内得到value，因此，哈希表常用来统计频率、快速检验某个元素是否出现过等。

思路

题中给出的信息是两副牌，因此最多4个零，因此必有一张非零牌，分析顺子两点基本情况：

• 不能由重复的非零牌

• 非零牌之间最大相差为4（也就是说，中间还有三个位置，可以填上三个数，让这五个牌成为顺子）

可以找到这手牌的最大差值

• 若是两张非零牌最大相差大于4，则需要更多的牌（大于三张）来填充中间的部分

• 若是小于等于4，又不重复的情况下，要么零牌补齐，要么本身就是相邻的数字

举几个例子
0 0 0 1 2
0 0 0 1 5
0 0 2 3 5

因此创建一个哈希表，查找重复：遍历数组的同时，遇到非零牌重复，直接return false，若没有重复，则加入哈希表中，等待后序的查找。同时在遍历过程中需要记录数组的最大值与最小值，最后检查最大值与最小值的差是否大于4，小于4的话，在没有 非零牌重复的情况下，最大值与最小值中间的牌加上0牌就可以填满这手顺子

一共五张扑克牌，只要最大值和最小值之间的距离小于等于4，那么不管是用非零牌，还是零牌，都可以构成顺子，构成顺子的有可能是零牌，也可能就是最大最小值之间的数本身

具体步骤

1. 创建一个哈希表，统计这手牌有无非零重复牌
2. 使用两个变量记录这手牌的上下界
3. 遍历每一张牌，零牌可以重复，非零牌重复则不能为顺子。用哈希表检查去重
4. 将新牌加入哈希表，并更新这手牌的上下界
5. 最后检查上下界之差是否大于5，若是，则构不成顺子，否则，可以。

import java.util.HashMap;

public class Solution {
    public boolean IsContinuous(int[] numbers) {

        int minValue = 100;
        int maxValue = -1;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int number : numbers) {

            //非零牌
            if (number != 0) {

                //非零牌重复，return false
                if (map.containsKey(number)) {
                    return false;
                }

                map.put(number, 1);

                //记录最大值
                if (number > maxValue) {
                    maxValue = number;
                }

                //记录最小值
                if (number < minValue) {
                    minValue = number;
                }
            }
        }
        return maxValue - minValue <= 4;
    }
}

方案二 排序

对数组先进行排序，这样如果有零牌，那么都会在数组的最前面

遍历数组，计算零牌出现的次数，以及当非零牌不止一个时，计算相邻两张非零牌之间的间隔，若间隔数大于零牌数，则不能组成顺子

就比如

【 0 0 0 2 4 】
2和4之间的间隔是1 ，零牌有3张，可以构成顺子
【 0 2 4 5 7 9】
2和4之间的间隔是1，5和7之间的间隔是1，7和9之间的间隔是1，零牌只有1张，无法构成顺子

import java.util.Arrays;

public class Solution {
    public boolean IsContinuous(int[] numbers) {

        Arrays.sort(numbers);

        //用于记录五个数中0出现的次数
        int zeros = 0;

        //用于记录所有的相邻两个数之间还能塞下几个数
        //比如1 3 4 5 6，cnt2 = 1，因为只有1和3之间还能塞下2
        int gap = 0;

        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] == 0) {
                zeros++;
                continue;
            }

            if (i != 0 && numbers[i] == numbers[i - 1]) {
                return false;
            }

            if (i != 0 && numbers[i - 1] != 0) {
                if (numbers[i] - numbers[i - 1] > 1) {
                    gap += (numbers[i] - numbers[i - 1] - 1);
                }
            }
        }
        return gap <= zeros;
    }
}