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

从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。

 

示例 1:

输入: [1,2,3,4,5]
输出: True  

示例 2:

输入: [0,0,1,2,5]
输出: True  

限制：

数组长度为 5 

数组的数取值为 [0, 13] .

---

一次遍历+哈希表

class Solution {
public:
    bool isStraight(vector<int>& nums) {
        int min_num = INT_MAX;
        int max_num = INT_MIN;
        int num_table[14];
        memset(num_table, 0, sizeof(num_table));
        for (int i = 0; i < nums.size(); i++) {
            num_table[nums[i]]++;
            if (nums[i] == 0) continue;     //0不参与最大最小值的计算
            if (num_table[nums[i]] > 1) return false;     //如果有非0的重复数，直接返回false
            min_num = min(nums[i], min_num);
            max_num = max(nums[i], max_num);
        }
        // for (int i = min_num; i <= max_num; i++) {
        //     num_table[i]--; 
        //     if (num_table[i] == -1 && num_table[0] > 0) {
        //         num_table[i]++;
        //         num_table[0]--;
        //     }
        //     if (num_table[i] != 0) return false; 
        // }
        // 只要最大最小值差异小于5即说明可组成顺子
        return max_num - min_num < 5;


    }
};

排序+一次遍历

class Solution {
public:
    bool isStraight(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        for (auto num : nums) cout << num << " ";
        int min_index = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == 0) {
                min_index++;
                continue;
            }
            if (i+1 < nums.size() && nums[i] == nums[i+1]) return false;
        }
        cout << min_index << endl;
        if (min_index == nums.size()) return true;
        // 只要最大最小值差异小于5即说明可组成顺子
        return nums[nums.size()-1] - nums[min_index] < 5;
    }
};