题解 | #扑克牌顺子#

题解一:排序+遍历
顺子牌的特点：
1、顺子一定没有相等的牌；
2、顺子中两张相邻的扑克牌的数值差为1，即满足interrapt=numbers[i + 1] - numbers[i] - 1==0;
3、当interrapt不为0，代表需要在顺子中插入对应interrapt张牌；
4、只有两张王牌；
主要思路：
1、排序五张牌；
2、遍历5张牌，并求出大小王的数量zero_num，与interrapt的大小；
3、判断interrapt的大小。
(1)interrapt==0,除大小王之外的牌本来就是顺子，大小王随便补齐在头部或者尾部；
(2)interrapt<=zero_num,除大小王之外的牌不是顺子，可以通过大小王变成特定的牌补在其中，使其成为顺子；
(2)interrapt>zero_num,除大小王之外的牌不是顺子,即使有大小王也补不成顺子。

对示例【16,0,2,0,4】进行演示

只要0少于需要补的数，即满足顺子的条件；

复杂度分析:
n=5,常数；
时间复杂度:O(1)
空间复杂度:O(1)

实现如下:

class Solution {
public:
    bool IsContinuous( vector<int> numbers ) {
        sort(numbers.begin(), numbers.end());
        int zero_num = 0;//统计大小王数量
        int i = 0;
        while (numbers[i] == 0)zero_num++,i++;
        int interrapt = 0;//记录五张牌中最大值max到最小值min的距离
        for (; i < numbers.size()-1; ++i) {
            if (numbers[i] == numbers[i + 1])return false;//出现相同的扑克牌
            interrapt += numbers[i + 1] - numbers[i] - 1;//计算距离
        }
        if (zero_num >= interrapt) return true;
        return false;
    }
};

题解二：采用set+遍历
主要条件：
1、与题解一一致的条件，顺子一定没有相等的牌；
2、顺子中最大的牌点数max - 顺子中最小的牌点数min < 5

算法流程：
1、遍历五张牌(遇到大小王，跳过)，将5张牌加入set；
2、如果在set中出现重复，即返回false，不构成顺子(题解一采用排序，可以处理出来)；
3、并且在遍历过程中获得最大值与最小值；

对示例【16,0,2,0,4】进行演示，在hash表中，红色代表已经出现过，蓝色代表未出现：

如上图所示，最后结果max=6，min=2，满足顺子中最大的牌点数max - 顺子中最小的牌点数min < 5，返回true的结果；

复杂度分析:
n=5,常数；
时间复杂度:O(1)
空间复杂度:O(1)

实现如下：

class Solution {
public:
    bool IsContinuous( vector<int> numbers ) {
        set<int> se;
        int _min=14,_max=0;//一副牌最大K点，所以_min初始化14；
        for(auto i:numbers){//C++11语法
            if(i==0)continue;//大小王
            _min=min(_min,i);//最小牌
            _max=max(_max,i);//最大牌
            if(se.count(i))return false;//出现重复牌
            se.insert(i);
        }
        return _max-_min<5;//顺子中最大的牌点数max - 顺子中最小的牌点数min < 5
    }
};

题解三：位运算充当set判断重复+遍历(类似于bitmap)
主要思路：同题解二；
不同点：采用一个int整数代替set去执行判断牌是否重复；
由于扑克牌是0-14的数字，而一个int数字有32位，我们可以使用int的低13位bit是否为1来判断这张牌是否已经出现过。
具体操作：
1、flag&(1<<numbers[i])判断牌是否已经重复；
2、flag|="(1<<numbers[i])标记此牌已经出现过；

复杂度分析:
n=5,常数；
时间复杂度:O(1) ，数组大小为5
空间复杂度:O(1),借用了一个int整数

class Solution {
public:
    bool IsContinuous( vector<int> numbers ) {
        int flag=0;//标记整数；
        int _min=14,_max=0;
        for(auto i:numbers){
            if(i==0)continue;//大小王
            _min=min(_min,i);//最小牌
            _max=max(_max,i);//最大牌
            if((flag&(1<<i))!=0)return false;//出现重复牌
            flag|=(1<<i);
        }
        return _max-_min<5;//顺子中最大的牌点数max - 顺子中最小的牌点数min < 5
    }
};