算法的学习笔记—扑克牌顺子(牛客JZ61)

😀前言
扑克牌顺子问题是一道趣味性与逻辑性兼备的题目，要求判断五张牌是否能组成顺子，其中大小王（癞子）可作为任意牌面。癞子的特殊性增加了问题的复杂度，也为解题提供了更多的可能性。通过这一问题，我们可以深入了解排序、计数以及差值计算在算法中的实际应用。

🏠个人主页：尘觉主页

61. 扑克牌顺子

题目链接

NowCoder

问题描述

在扑克牌游戏中，顺子是指五张连续的牌（大小顺序不限）。题目要求给出五张牌，其中大小王（癞子）可以充当任何牌面（表示为 0），判断这五张牌是否能够组成顺子。为了更加清晰，我们先明确顺子的两个关键条件：

1. 牌面不重复（癞子除外）。
2. 最大牌和最小牌的差值小于 5（癞子可以填补间隙）。

解题思路

本题可以通过以下步骤实现：

1. 对数组进行排序

首先，对输入的数组进行排序。这样可以轻松计算非连续的间隙，并便于处理逻辑。

2. 统计癞子（大小王）的数量

遍历数组，统计牌面为 0 的牌的数量，即癞子数量 cnt。

3. 判断是否满足顺子的条件

从非癞子牌开始遍历，依次检查两张相邻牌之间的差值。如果存在重复牌，直接返回 false。否则，利用癞子填补两张牌之间的差值：

• 如果间隙大小大于癞子数量，则无法组成顺子；
• 否则，继续检查，直到所有牌都被验证。

4. 返回结果

最终，若癞子数量足够填补间隙，返回 true；否则返回 false。

代码实现

以下是基于上述思路的 Java 代码：

public boolean isContinuous(int[] nums) {// 如果牌的数量少于5张，直接返回falseif (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++) {// 如果存在重复牌，返回falseif (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(nlog⁡n)，遍历数组的复杂度为 O(n)。因此总体复杂度为 O(nlog⁡n)。
• 空间复杂度：排序时需要额外的存储空间，复杂度为 O(1)。

😄总结

通过本题，我们学习了如何结合排序和计数来解决扑克牌顺子问题。利用癞子的特殊性质，有效地填补间隙，最终判断是否满足顺子的条件。这一思路可以扩展到其他类似问题，如跳跃游戏或间隙填补问题。

😁热门专栏推荐
想学习vue的可以看看这个

java基础合集

数据库合集

redis合集

nginx合集

linux合集

手写机制

微服务组件

spring_尘觉

springMVC

mybits

等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持

🤔欢迎大家加入我的社区 尘觉社区

文章到这里就结束了，如果有什么疑问的地方请指出，诸佬们一起来评论区一起讨论😁
希望能和诸佬们一起努力，今后我们一起观看感谢您的阅读🍻
如果帮助到您不妨3连支持一下，创造不易您们的支持是我的动力🤞