题解 | #扑克牌顺子#

题目：扑克牌顺子

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

思路分析：在读题目的同时，我们应该去思考在什么情况下，扑克牌的五张牌不能构成顺子，同时也应该去思考解题的方法与技巧。

解法一：首先判断扑克牌要进行排序的张数，是否符合题目要求，如果是不符合题目要求的张数，可以直接返回false。在符合题目要求的同时，我们可以将扑克牌中的大小王（任意张）的个数计算出来，将扑克牌的顺序按大小排序完整后，进行下一轮的问题思考。

其次，可以想象一个问题，在两副牌中有四个大小王，所以可以分析如下情况：

当五张牌只有一张王的时候，按照大小顺序排序后，王应该在最前面，剩下的四张牌的大小其中相邻两张之间不能超过2，而且只能存在一次这种情况的发生，如果超过2，则直接返回false，例如0，1，4，5，6，如果没有超过，则返回true。

以此类推，有两张王的时候，剩下的四张牌的大小相邻两张牌之间不能超过3，或者有相邻两个两张牌之间的差距不能超过1，以此类推，就发现了解决问题的关键。

例子具体分析如下所示：

根据判断可得，4-2-1 = 1，6-2-1 = 1，将两个值的大小相加后，与0的个数做比较：

当0的个数大于两个值的和时，返回true。

当0的个数小于两个值的和时，返回false。

当0的个数等于两个值的和时，返回true，由这几条可知该实例最后返回的结果为true。

其中C++代码如下所示：

class Solution {
public:
    bool IsContinuous( vector<int> numbers ) {
        if(numbers.size() != 5)
            return false;
        sort(numbers.begin(), numbers.end());
        int numzero = 0;
        for(int i = 0; i != 5;i ++){//判断0的个数
            if(!numbers[i])
                numzero++;
        }
        
        int target = numzero + 1;//下标数
        int numgap = 0;
        while(target < 5){
            if(numbers[target - 1] == numbers[target])//像对子这种意外情况的发生
                return false;
            numgap += numbers[target] - numbers[target - 1] - 1;
            target++;
        }
        return (numzero >= numgap) ? true : false;
    }
};

时间复杂度为O(N)。

解法2：我们通过观察可以发现一个常识性的问题就是，因为是顺子，所以其最大值和最小值的差值不会超过5（不能允许有对的情况出现）。

以上述例子为例：

该方法C++代码如下所示：

class Solution {
public:
    bool IsContinuous( vector<int> numbers ) {
        int numzero = 0;
        sort(numbers.begin(), numbers.end());
        for(int i = 0; i < 5;i++){
            if(numbers[i] == 0)
                numzero++;
            else if(numbers[i] == numbers[i+1])
                return false;
        }
        return numbers[4] - numbers[numzero] < 5;
    }
};