剑指 Offer 61. 扑克牌中的顺子

用一个长度为14的数组记录，每个值的个数，遍历数组记录的同时排除值重复的情况

遍历记录个数的数组：

• 若没有当前值，且没joker，则返回false
• 若没有当前值，有joker，则使用一个joker，joker的数量减1，继续遍历
• 遍历完成都没返回，说明可以组成顺子

class Solution {
public:
    bool isStraight(vector<int>& nums) {
        int arr[14] = { 0 };
        for (int num : nums) {
            arr[num]++;
        }
        int start = 1;
        int joker = arr[0];
        while (start < 14) {
            if (arr[start] == 0) {
                // 没有当前值，往后找
                start++;
            }
            else if (arr[start] == 1) {
                // 找到一个值了，开始查看后4个能否组成顺子
                break;
            }
            else {
                // 值重复，不能组成顺子
                return false;
            }
        }
        int cur = start;
        while (cur <= start + 4 && cur < 14) {
            if (arr[cur] > 1 || (arr[cur] == 0 && joker == 0)) {
                // 有重复的 || 没有当前值，没joker了
                return false;
            }
            if (arr[cur] == 0 && joker > 0) {
                // 没有当前值，有joker
                joker--;
            }
            cur++;
        }
        // 5个遍历完，值都存在，可以组成顺子
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

集合 Set + 遍历

• 遍历五张牌，遇到 joker（即 0 ）直接跳过。
• 判别重复： 利用 Set 实现遍历判重， Set 的查找方法的时间复杂度为 O(1) ；
• 获取最大 / 最小的牌： 借助辅助变量 max 和 min ，遍历统计即可

class Solution {
public:
    bool isStraight(vector<int>& nums) {
        unordered_set<int> st;
        int max_ = nums[0];   // 这里的最大最小值，指的是除了jokere以外的最大最小值
        int min_ = 13;        // 最小值不能为0，初始化为最大的13
        for (int num : nums) {
            if (num == 0) {
                continue;
            }
            if (st.count(num) > 0) {
                // 重复，不能组成顺子
                return false;
            }
            st.insert(num);
            max_ = max(max_, num);
            min_ = min(min_, num);
        }
        // 不重复，最大值-最小值 < 5，必能组成顺子
        return max_ - min_ < 5;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

排序 + 遍历

• 判别重复： 排序数组中的相同元素位置相邻，因此可通过遍历数组，判断 nums[i] = nums[i + 1] 是否成立来判重。
• 获取最大 / 最小的牌： 排序后，数组末位元素 nums[4] 为最大牌；元素 nums[joker] 为最小牌，其中 joker 为大小王的数量

class Solution {
public:
    bool isStraight(vector<int>& nums) {
        sort(nums.begin(), nums.end(), less<int>());
        int joker = 0;
        for(int i = 0; i < 5; i++){
            if(nums[i] == 0){
                joker++;
            }else if(i < 4 && nums[i] == nums[i+1]){
                return false;
            }
        }
        if (joker == 5) {
            return true;
        }
        // 不重复，最大值-最小值 < 5，必能组成顺子
        return nums[4] - nums[joker] < 5;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    bool isStraight(vector<int>& nums) {
        sort(nums.begin(), nums.end(), less<int>());
        int joker = 0;
        for(int i = 0; i < 4; i++){
            if(nums[i] == 0){
                joker++;
            }else if(nums[i] == nums[i+1]){
                return false;
            }
        }
        // 不重复，最大值-最小值 < 5，必能组成顺子
        return nums[4] - nums[joker] < 5;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

集合 Set / 排序，清晰图解