LeetCode 剑指 Offer 61. 扑克牌中的顺子
题目描述
题意分析
五张牌可以重新排列，要判断能否把它们全部排成五个连续的整数。
A按1计算，J、Q、K分别按11、12、13计算；大小王用0表示，每张都可以独立替代一个需要的数。这里不要求原来的排列顺序连续，也不能丢掉某张牌。普通牌的点数不能改变，因此相同的非零点数出现两次时一定无解；多个
0则可以替代不同点数。只需返回是否可能，不需要输出具体排列或大小王的替代值。
解法：排序后检查重复和跨度
核心思路
[!blue]
先排序，使所有
0集中在开头，非零牌按从小到大的顺序排列。这样既能通过相邻比较发现重复，也能直接找到最小和最大的非零点数。排序会改变输入数组，但题目并不要求保留原顺序。顺子中的点数各不相同，所以非零牌重复时直接失败。没有重复后，设非零牌有
q张，最小值为min，最大值为max。从min到max一共有max - min + 1个整数位置，其中已有q张普通牌，内部缺口数就是max - min + 1 - q。大小王共有
5 - q张。能填满内部缺口，等价于max - min + 1 - q <= 5 - q，化简后就是max - min < 5。多余的大小王可以补在连续区间两端，把总长度扩到五张；因此“非零牌不重复、最大最小非零点数之差小于五”既是必要条件，也是充分条件。
0只负责补牌，不能参与重复或最小值计算。如果跳过所有0后已经没有普通牌，直接返回true，无需再读取最小值。
解题步骤
- 将数组升序排序。
- 用
first跳过开头所有0，使它指向最小的非零牌；若已到数组末尾，返回true。- 从
first + 1开始检查相邻牌，发现相同的非零点数就返回false。- 最后一个元素是最大非零牌，返回
nums[nums.length - 1] - nums[first] < 5的判断结果。
代码实现
class Solution {
public boolean isStraight(int[] nums) {
Arrays.sort(nums);
int first = 0;
// 零是万能牌，不参与重复判断和最小非零值的计算。
while (first < nums.length && nums[first] == 0) {
first++;
}
if (first == nums.length) {
return true;
}
for (int i = first + 1; i < nums.length; i++) {
if (nums[i] == nums[i - 1]) {
return false;
}
}
// 非零值互异且跨度不足五，剩余缺口就能由万能牌补齐。
return nums[nums.length - 1] - nums[first] < 5;
}
}
import "sort"
func isStraight(nums []int) bool {
sort.Ints(nums)
first := 0
// 零是万能牌，不参与重复判断和最小非零值的计算。
for first < len(nums) && nums[first] == 0 {
first++
}
if first == len(nums) {
return true
}
for i := first + 1; i < len(nums); i++ {
if nums[i] == nums[i-1] {
return false
}
}
// 非零值互异且跨度不足五，剩余缺口就能由万能牌补齐。
return nums[len(nums)-1]-nums[first] < 5
}
复杂度分析
- 时间复杂度：
O(1)。本题始终只有五张牌，排序和扫描的处理量都有固定上界。- 空间复杂度：
O(1)。只使用几个变量，固定长度排序所需的辅助空间也是常数。
关键点总结
[!green]
- 先处理重复，再判断跨度；大小王能填空位，不能消除普通牌的重复。
- 跨度条件来自“内部缺口数不超过大小王数量”，不需要逐张安排大小王。
- 排序只用于把零、重复点数和两个端点集中到容易检查的位置，原数组会被修改。
易错点总结
[!yellow]
- 把
0当作最小点数：会把大小王与普通牌之间的距离误算成真实缺口，最小值必须取第一张非零牌。- 把多个
0判为重复：大小王可以分别替代不同数，重复检查只针对非零牌。- 将跨度条件写成
<= 5：五个连续整数的最大差为四，差为五时至少需要六个位置。- 只检查跨度：普通牌有重复时，即使跨度很小也不能组成五个不同的连续点数。
- 跳过零后直接访问数组：全部为零时
first已到末尾，必须先返回，避免越界。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 846. 一手顺子 | 中等 | 原题把全部牌分成固定长度顺子且没有大小王，本题只检查五张牌并用0补缺，重复非零牌仍不能成顺子。 |
| 128. 最长连续序列 | 中等 | 连续数值关系可复用，但本题牌数固定且存在通配0，不能只取去重后的最长连续段。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！