剑指offer(C++)-JZ61：扑克牌顺子(算法-模拟)

作者：翟天保Steven
版权声明：著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处

题目描述：

现在有2副扑克牌，从扑克牌中随机五张扑克牌，我们需要来判断一下是不是顺子。
有如下规则：
1. A为1，J为11，Q为12，K为13，A不能视为14
2. 大、小王为 0，0可以看作任意牌
3. 如果给出的五张牌能组成顺子（即这五张牌是连续的）就输出true，否则就输出false。
4.数据保证每组5个数字，每组最多含有4个零，数组的数取值为 [0, 13]

要求：空间复杂度 O(1)，时间复杂度O(nlogn)，本题也有时间复杂度O(n) 的解法

示例：

输入：

[6,0,2,0,4]

返回值：

true

说明：

中间的两个0一个看作3，一个看作5 。即：[6,3,2,5,4]
这样这五张牌在[2,6]区间连续，输出true 

解题思路：

本题考察算法场景模拟。两种解题思路。

1）排序法

       将卡牌排序，复杂度O(nlogn)，遍历一次O(n)，记录0的数量，如果出现重复数据则中断返回false，对非0非重复数据进行间隔累加。如果最终0的数量大于等于间隔累加数，则说明可以形成顺子。

       比如2 0 4 0 0 7，排序后0 0 0 2 4 7，2和4间隔1,4和7间隔2，三个0刚好补齐，多余的0可以在前后凑顺子。

      如果0的数量和输入数量一致，则无法形成顺子。

      总的复杂度O(nlogn+n)，即O(nlogn)。

2）查找法

       进行双层循环。发现0则跳过；通过set的count函数检测是否遇到重复，重复则返回false；无问题则插入数值，同时刷新最值。

       如果能持续到循环结束，此时最大值减去最小值的差值小于5，则一定能构成顺子，反之则不行。

       时间复杂度O(n2)，遍历为n，查找为n，即n*n。

3）查找法进阶

       与查找法流程基本一致，区别在于检测重复值。因为卡牌最多只有0-14这15个数字，我们充分利用位运算特性，如果遇到某个数值，比如5，则将bm的第五位设为1，即0001 0000，每次遇到一个新数值就刷新bm。

       这样可以用&运算检测是否重复，只有某一位都为1，才会触发重复标识，进而返回false。用|运算刷新bm。

       时间复杂度O(n)，遍历为n，查找为1，即n*1。

测试代码：

1）排序法

class Solution {
public:
    // 是否顺子
    bool IsContinuous(vector<int>& numbers) {
        // 排序法
        // 时间复杂度O(nlogn+n)=O(nlogn)
        // 快速排序
        sort(numbers.begin(), numbers.end());
        int size = int(numbers.size());
        int zeroNum = 0;
        int diff = 0;
        for(int i = 0; i < size; ++i){
            // 记录0的数量
            if(numbers[i] == 0){
                zeroNum++;
            } 
            // 判断是否有重复数据
            else if(i > 0 && numbers[i - 1] == numbers[i]){
                return false;
            }
            // 累加间隔长度，注意0不参与间隔计算
            else if(i > 0 && numbers[i - 1] != 0){
                // 比如2和3之间无多余间隔，则diff累加0；2和4之间有3这一个间隔，diff累加1
                diff += numbers[i] - numbers[i - 1] - 1;
            }
        }
        // 0的数量只有大于等于多余的间隔长度，才能凑成顺子
        if(zeroNum == size){
            return false;
        }
        else if(zeroNum >= diff){
            return true;
        }
        else{
            return false;
        }
    }
};

2）查找法

class Solution {
public:
    // 是否顺子
    bool IsContinuous(vector<int>& numbers) {
        // 查找法
        // 时间复杂度O(n2)
        int size = int(numbers.size());
        set<int> s;
        int minNum = 13;
        int maxNum = 0;
        for(int i = 0; i < size; ++i){
            // 跳过0
            if(numbers[i] == 0){
                continue;
            } 
            // 检查重复值，复杂度O(n)
            if(s.count(numbers[i])){
                return false;
            }
            // 插入
            s.insert(numbers[i]);
            // 刷新最值
            minNum = min(minNum, numbers[i]);
            maxNum = max(maxNum, numbers[i]);
        }
        // 最大值和最小值之差小于5，则一定能构成顺子
        bool result = (maxNum - minNum) < 5;
        return result;
    }
};

3）查找法进阶

class Solution {
public:
    // 是否顺子
    bool IsContinuous(vector<int>& numbers) {
        // 查找法进阶
        // 时间复杂度O(n)
        int size = int(numbers.size());
        int bm = 0;
        int minNum = 13;
        int maxNum = 0;
        for(int i = 0; i < size; ++i){
            // 跳过0
            if(numbers[i] == 0){
                continue;
            } 
            // 检查重复值，复杂度O(1)
            if((bm & (1 << numbers[i])) != 0){
                return false;
            }
            // 数字对应位改为1
            bm |= (1 << numbers[i]);
            // 刷新最值
            minNum = min(minNum, numbers[i]);
            maxNum = max(maxNum, numbers[i]); 
        }
        // 最大值和最小值之差小于5，则一定能构成顺子
        bool result = (maxNum - minNum) < 5;
        return result;
    }
};