題⽬描述

撲克牌可以組成順⼦，⼤\⼩ 王可以看成任何數字,並且 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)，只使用固定數量的整數變量