【牛客剑指offer】JZ61扑克牌顺子两种方案Java实现

剑指offer题解汇总 Java实现

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

本题链接

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

题目

题目主要信息

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

方案一 哈希表

哈希表

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

思路

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

• 不能由重复的非零牌

• 非零牌之间最大相差为4&＃xff08;也就是说&＃xff0c;中间还有三个位置&＃xff0c;可以填上三个数&＃xff0c;让这五个牌成为顺子&＃xff09;

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

• 若是两张非零牌最大相差大于4&＃xff0c;则需要更多的牌&＃xff08;大于三张&＃xff09;来填充中间的部分

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

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

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

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

具体步骤

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

import java.util.HashMap;public class Solution {public boolean IsContinuous(int[] numbers) {int minValue &＃61; 100;int maxValue &＃61; -1;HashMap<Integer, Integer> map &＃61; new HashMap<>();for (int number : numbers) {//非零牌if (number !&＃61; 0) {//非零牌重复&＃xff0c;return falseif (map.containsKey(number)) {return false;}map.put(number, 1);//记录最大值if (number > maxValue) {maxValue &＃61; number;}//记录最小值if (number < minValue) {minValue &＃61; number;}}}return maxValue - minValue <&＃61; 4;}
}

方案二 排序

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

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

就比如

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

import java.util.Arrays;public class Solution {public boolean IsContinuous(int[] numbers) {Arrays.sort(numbers);//用于记录五个数中0出现的次数int zeros &＃61; 0;//用于记录所有的相邻两个数之间还能塞下几个数//比如1 3 4 5 6&＃xff0c;cnt2 &＃61; 1&＃xff0c;因为只有1和3之间还能塞下2int gap &＃61; 0;for (int i &＃61; 0; i < numbers.length; i&＃43;&＃43;) {if (numbers[i] &＃61;&＃61; 0) {zeros&＃43;&＃43;;continue;}if (i !&＃61; 0 && numbers[i] &＃61;&＃61; numbers[i - 1]) {return false;}if (i !&＃61; 0 && numbers[i - 1] !&＃61; 0) {if (numbers[i] - numbers[i - 1] > 1) {gap &＃43;&＃61; (numbers[i] - numbers[i - 1] - 1);}}}return gap <&＃61; zeros;}
}