😀前言
扑克牌顺子问题是一道趣味性与逻辑性兼备的题目,要求判断五张牌是否能组成顺子,其中大小王(癞子)可作为任意牌面。癞子的特殊性增加了问题的复杂度,也为解题提供了更多的可能性。通过这一问题,我们可以深入了解排序、计数以及差值计算在算法中的实际应用。
🏠个人主页:尘觉主页
文章目录
- 61. 扑克牌顺子
- 题目链接
- 问题描述
- 解题思路
- 1. 对数组进行排序
- 2. 统计癞子(大小王)的数量
- 3. 判断是否满足顺子的条件
- 4. 返回结果
- 代码实现
- 代码解析
- 1. 排序数组
- 2. 统计癞子数量
- 3. 检查间隙并填补
- 4. 返回结果
- 示例
- 示例 1
- 示例 2
- 示例 3
- 时间和空间复杂度
- 😄总结
61. 扑克牌顺子
题目链接
NowCoder
问题描述
在扑克牌游戏中,顺子是指五张连续的牌(大小顺序不限)。题目要求给出五张牌,其中大小王(癞子)可以充当任何牌面(表示为 0),判断这五张牌是否能够组成顺子。为了更加清晰,我们先明确顺子的两个关键条件:
- 牌面不重复(癞子除外)。
- 最大牌和最小牌的差值小于 5(癞子可以填补间隙)。
解题思路
本题可以通过以下步骤实现:
1. 对数组进行排序
首先,对输入的数组进行排序。这样可以轻松计算非连续的间隙,并便于处理逻辑。
2. 统计癞子(大小王)的数量
遍历数组,统计牌面为 0 的牌的数量,即癞子数量 cnt
。
3. 判断是否满足顺子的条件
从非癞子牌开始遍历,依次检查两张相邻牌之间的差值。如果存在重复牌,直接返回 false
。否则,利用癞子填补两张牌之间的差值:
- 如果间隙大小大于癞子数量,则无法组成顺子;
- 否则,继续检查,直到所有牌都被验证。
4. 返回结果
最终,若癞子数量足够填补间隙,返回 true
;否则返回 false
。
代码实现
以下是基于上述思路的 Java 代码:
public boolean isContinuous(int[] nums) {
// 如果牌的数量少于5张,直接返回false
if (nums.length < 5)
return false;
// 对数组进行排序
Arrays.sort(nums);
// 统计癞子数量
int cnt = 0;
for (int num : nums) {
if (num == 0)
cnt++;
}
// 检查牌间的间隙,利用癞子进行填补
for (int i = cnt; i < nums.length - 1; i++) {
// 如果存在重复牌,返回false
if (nums[i + 1] == nums[i])
return false;
// 计算间隙大小,并用癞子填补
cnt -= nums[i + 1] - nums[i] - 1;
}
// 如果癞子足够填补间隙,则为顺子
return cnt >= 0;
}
代码解析
1. 排序数组
通过 Arrays.sort(nums)
,我们将数组按从小到大的顺序排列,使间隙的计算更加方便。
2. 统计癞子数量
通过遍历数组统计 nums
中的癞子数量 cnt
:
int cnt = 0;
for (int num : nums) {
if (num == 0)
cnt++;
}
3. 检查间隙并填补
从非癞子牌开始遍历,通过以下逻辑处理:
- 重复牌检查:如果两张相邻牌相等,则无法形成顺子,直接返回
false
。 - 间隙填补:计算间隙大小
nums[i + 1] - nums[i] - 1
,并减少癞子数量。
如果癞子数量不足以填补所有间隙,则返回 false
;否则,继续检查。
4. 返回结果
当遍历完成且癞子数量能够填补所有间隙时,返回 true
。
示例
以下是几个测试用例及其输出:
示例 1
输入:[1, 2, 3, 4, 5]
输出:true
解释:五张牌是连续的,不需要癞子。
示例 2
输入:[0, 0, 1, 2, 5]
输出:true
解释:两张癞子可以填补 3 和 4 的位置。
示例 3
输入:[0, 0, 2, 2, 5]
输出:false
解释:存在重复的非癞子牌,无法形成顺子。
时间和空间复杂度
- 时间复杂度:排序的时间复杂度为 O(nlogn),遍历数组的复杂度为 O(n)。因此总体复杂度为 O(nlogn)。
- 空间复杂度:排序时需要额外的存储空间,复杂度为 O(1)。
😄总结
通过本题,我们学习了如何结合排序和计数来解决扑克牌顺子问题。利用癞子的特殊性质,有效地填补间隙,最终判断是否满足顺子的条件。这一思路可以扩展到其他类似问题,如跳跃游戏或间隙填补问题。
😁热门专栏推荐
想学习vue的可以看看这个
java基础合集
数据库合集
redis合集
nginx合集
linux合集
手写机制
微服务组件
spring_尘觉
springMVC
mybits
等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持
🤔欢迎大家加入我的社区 尘觉社区
文章到这里就结束了,如果有什么疑问的地方请指出,诸佬们一起来评论区一起讨论😁
希望能和诸佬们一起努力,今后我们一起观看感谢您的阅读🍻
如果帮助到您不妨3连支持一下,创造不易您们的支持是我的动力🤞