剑指offer-45、扑克牌顺⼦

题⽬描述

扑克牌可以组成顺⼦，⼤\⼩ 王可以看成任何数字,并且 A 看作 1 , J 为 11 , Q 为 12 , K 为 13 。 5张牌 【A,0,3,0,5】 就可以变成“ 1,2,3,4,5 ”(⼤⼩王分别看作 2 和 4 ),这样就组成了顺⼦。（可以认为⼤⼩王是 0 。）

输⼊五张牌，如果牌能组成顺⼦就输出true，否则就输出 false 。

示例1
输⼊：[0,3,2,6,4]
返回值：true

思路及解答

排序遍历

这是最直观的解法，通过排序后分析牌之间的间隔关系来判断。

排序后统计大小王数量，检查非王牌之间的间隔是否可用大小王填补：先排序，0肯定是靠左边，然后统计0的个数，后⾯的数，按照第⼀个⾮0的数进⾏递增，如果不是递增，则需要使⽤ 0 牌补充，如果 0 牌不够，需要放回 false ，否则直到遍历完数组，返回true 。

public boolean IsContinuous(int[] numbers) {
    // 数组⻓度不符合直接返回
    if (numbers == null || numbers.length < 5) {
        return false;
    }
    // 先排序
    Arrays.sort(numbers);
    // 统计0的个数
    int numOfZero = 0;
    // 初始化索引
    int start;
    // 统计0的个数
    for (start = 0; start < numbers.length; start++) {
        if (numbers[start] == 0) {
            numOfZero++;
        } else {
            // ⾮0的时候跳出
            break;
        }
        // 暂存0的个数
        int n = numOfZero;
        // 当前的数值
        int cur = numbers[numOfZero];
        // 从0的下两个位置开始
        for (start++; start < numbers.length;) {
            // 如果可变的牌数量为0
            if (numOfZero == 0) {
                // 和前⾯的⼀个对⽐
                if (numbers[start] != cur + 1) {
                    // 不等于当前数值+1的话，直接返回false
                    return false;
                } else {
                    // 当前数值+1
                    cur++;
                }
            } else {
                // 不等于当前数值+1的话，直接返回false
                if (numbers[start] != cur + 1) {
                    // 可变牌数量-1
                    numOfZero--;
                    //当前值+1
                    cur++;
                    // 遍历下⼀张牌
                    continue;
                } else {
                    // 相等则直接将当前值+1
                    cur++;
                }
            }
            // 索引滑动到下⼀张牌
            start++;
        }
        return true;
    }
}

• 时间复杂度：O(n log n)，主要来自排序操作
• 空间复杂度：O(1)，只使用常数级别额外空间

哈希集合法（推荐）

利用HashSet实现去重，同时记录最大值和最小值。

初始化⼀个最⼩牌 14 ，最⼤牌 0 ，直接使⽤ set 保存数组的元素，如果 set 中已经存在该元素，那么我们直接放回 false ，如果 set 中不存在该元素，则将该元素放进 set 中，判断该元素是否⼩于最⼩牌，⼩于则更新最⼩牌，判断该元素是否⼤于最⼤牌，如果⼤于最⼤牌，则更新当前最⼤牌。

为什么 max - min < 5是充分必要条件？

对于5张牌组成的顺子：

• 如果是连续5张不同数字：max - min = 4
• 如果有空缺，但能被大小王填补：max - min ≤ 4
• 如果空缺太大：max - min ≥ 5，即使有4个大小王也无法填补

示例验证：

• [1,3,0,0,5]：max=5, min=1, 5-1=4<5 ✓
• [1,6,0,0,0]：max=6, min=1, 6-1=5≥5 ✗

public class Solution45 {
    public boolean IsContinuous(int[] numbers) {
        if (numbers == null || numbers.length < 5) {
            return false;
        }
        HashSet <Integer> set = new HashSet <> ();
        int min = 14;
        int max = 0;
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] != 0) {
                if (set.contains(numbers[i])) {
                    return false;
                }
                set.add(numbers[i]);
                max = Math.max(max, numbers[i]);
                min = Math.min(min, numbers[i]);
            }
        }
		// 关键条件：最大牌-最小牌 < 5 才能组成顺子
        return max - min < 5;
    }
}

• 时间复杂度：O(n)，只需遍历数组一次
• 空间复杂度：O(n)，HashSet的空间开销

位运算法（空间最优）

利用整数的二进制位来标记牌值是否出现，实现O(1)空间复杂度。

二进制位标记原理：

• 整数flag的32位中，用第i位表示数字i是否出现
• 例如：数字3出现 → 将第3位置1：flag |= 1 << 3
• 检查数字3是否出现：(flag >> 3) & 1 == 1

public class Solution {

    public boolean isStraight(int[] nums) {
        if (nums == null || nums.length != 5) {
            return false;
        }
        
        int flag = 0; // 用二进制位标记牌值出现情况
        int max = 0;  // 非王牌最大值
        int min = 14; // 非王牌最小值
        
        for (int num : nums) {
            if (num == 0) {
                continue; // 跳过大小王
            }
            
            // 检查牌值是否已出现（检查第num位是否为1）
            if (((flag >> num) & 1) == 1) {
                return false; // 有重复牌
            }
            
            // 标记牌值已出现（将第num位置为1）
            flag |= (1 << num);
            
            // 更新最值
            if (num > max) max = num;
            if (num < min) min = num;
            
            // 提前判断：如果已经不可能组成顺子，直接返回
            if (max - min >= 5) {
                return false;
            }
        }
        
        return max - min < 5;
    }
}

• 时间复杂度：O(n)，线性遍历
• 空间复杂度：O(1)，只使用固定数量的整数变量

本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top