文章目录
- 剑指offer题解汇总 Java实现
- 本题链接
- 题目
- 方案一 哈希表
- 方案二 排序
剑指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,那么不管是用非零牌,还是零牌,都可以构成顺子,构成顺子的有可能是零牌,也可能就是最大最小值之间的数本身
具体步骤
- 创建一个哈希表,统计这手牌有无非零重复牌
- 使用两个变量记录这手牌的上下界
- 遍历每一张牌,零牌可以重复,非零牌重复则不能为顺子。用哈希表检查去重
- 将新牌加入哈希表,并更新这手牌的上下界
- 最后检查上下界之差是否大于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 falseif (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之间还能塞下2int 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;}
}