题目描述：
现在有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; } };
