题解 | #扑克牌顺子#

扑克牌顺子

http://www.nowcoder.com/practice/762836f4d43d43ca9deb273b3de8e1f4

题目的主要信息：

两幅扑克牌抽5张，判断是否为顺子
A为1，J为11，Q为12，K为13
大、小王为 0，0可以看作任意牌

举一反三：

学习完本题的思路你可以解决如下题目：

JZ56. 数组中只出现一次的两个数字

JZ50. 第一个只出现一次的字符

方法一：哈希表（推荐使用）

知识点：哈希表

哈希表是一种根据关键码（key）直接访问值（value）的一种数据结构。而这种直接访问意味着只要知道key就能在 $O (1)$ 时间内得到value，因此哈希表常用来统计频率、快速检验某个元素是否出现过等。

思路：

题中给出的信息是两副牌，因此最多4个零，因此必有一张非零牌，分析顺子两点基本情况：

不能有重复的非零牌
非零牌之间最大相差为4

可以找到这手牌的最大差值，若是两张非零牌最大相差大于4，则需要4张零牌（超出了限制）来填充中间的部分，若是小于等于4，又不重复的情况下，要么零牌补齐，要么本身就是相邻的数字。

因此创建一个哈希表，查找重复：遍历数组的同时，遇到非零牌重复，直接不行，若没有重复则加入到哈希表中，等待后续的查找。同时在遍历过程需要记录数组最大值与最小值，最后检查最大值与最小值的差是否大于4，小于4的话，在没有非零牌重复的情况下，最大值与最小值中间的牌加上0牌就可以填满这手顺子。

具体做法：

step 1：创建一个哈希表统计这手牌有无非零重复牌。
step 2：使用两个变量记录这手牌的上下界。
step 3：遍历每一张牌，零牌可以重复，非零牌重复则不能为顺子。用哈希表检查去重。
step 4：将新牌加入哈希表，并更新这手牌的上下界。
step 5：最后检查上下界之差是否大于等于5，若是则构不成顺子，否则可以。

图示：

图片说明

Java实现代码：

import java.util.*;
public class Solution {
    public boolean IsContinuous(int [] numbers) {
        HashMap<Integer, Integer> hash = new HashMap<>();
        //设置顺子上下界
        int max = 0, min = 13;
        //遍历牌
        for(int i = 0; i < numbers.length; i++){
            if(numbers[i] > 0){
                //顺子不能重复
                if(hash.containsKey(numbers[i])) 
                    return false;
                else{
                    //将新牌加入哈希表
                    hash.put(numbers[i], i);
                    //更新上下界
                    if(numbers[i] >= max)
                        max = numbers[i];
                    if(numbers[i] <= min)
                        min = numbers[i];
                }
            }
        }
        //如果两张牌大于等于5，剩下三张牌无论如何也补不齐
        if((max - min) >= 5)  
            return false;
        else
            return true;
    }
}

C++实现代码：

class Solution {
public:
    bool IsContinuous( vector<int> numbers ) {
        unordered_map<int, int> hash;
        //设置顺子上下界
        int max = 0, min = 13;
        //遍历牌
        for(int i = 0; i < numbers.size(); i++){
            if(numbers[i] > 0){
                //顺子不能重复
                if(hash.find(numbers[i]) != hash.end()) 
                    return false;
                else{
                    //将新牌加入哈希表
                    hash[numbers[i]] = i; 
                    //更新上下界
                    if(numbers[i] >= max)
                        max = numbers[i];
                    if(numbers[i] <= min)
                        min = numbers[i];
                }
            }
        }
        //如果两张牌大于等于5，剩下三张牌无论如何也补不齐
        if((max - min) >= 5)  
            return false;
        else
            return true;
    }
};

Python实现代码：

class Solution:
    def IsContinuous(self , numbers: List[int]) -> bool:
        hash = dict()
        #设置顺子上下界
        max = 0
        min = 13
        #遍历牌
        for i in range(len(numbers)):
            if numbers[i] > 0:
                #顺子不能重复
                if numbers[i] in hash:
                    return False
                else:
                    #将新牌加入哈希表
                    hash[numbers[i]] = i
                    #更新上下界
                    if numbers[i] >= max:
                        max = numbers[i]
                    if numbers[i] <= min:
                        min = numbers[i]
        #如果两张牌大于等于5，剩下三张牌无论如何也补不齐
        if (max - min) >= 5:  
            return False
        else:
            return True

复杂度分析：

时间复杂度： $O (n)$ ，其中n$为数组长度，只遍历了一遍数组
空间复杂度： $O (n)$ ，创建的哈希表最坏大小为数组大小

方法二：排序法（扩展思路）

思路：

除了哈希表，还有更直观的方法。我们需要的顺子是连续的，那我们就对数组先进行一次排序，可以当作任意牌的0，都在前面，后面的如果是顺子就应该是连续的。

遍历数组，遇到零牌计数，遇到非零牌计算与其后的间隔数，最后比较零牌数与间隔数，若是间隔数大于零牌数则不能组成顺子。

step 1：优先对数组排序。
step 2：遍历数组，遇到零牌计数，遇到非零牌统计其与后一个是否相同，因为重复非零牌不能构成顺子。
step 3：计算当前非零牌与后一张相邻牌的间隔，并将所有间隔累加。
step 4：间隔数大于零牌数，则无法构成顺子。

Java实现代码：

import java.util.*;
public class Solution {
    public boolean IsContinuous(int [] numbers) {
        //先排序
        Arrays.sort(numbers); 
        int zero = 0;
        int gap = 0;
        for(int i = 0; i < numbers.length - 1; i++){ 
            //统计零牌数
            if(numbers[i] == 0) 
                zero++;
            else{
                //不可重复
                if(numbers[i + 1] - numbers[i] == 0) 
                    return false;
                else
                    //统计间隔数
                    gap += numbers[i + 1] - numbers[i] - 1; 
            }
        }
        //比较间隔与零牌数
        if(gap > zero)
            return false;
        else
            return true;
    }
}

C++实现代码：

class Solution {
public:
    bool IsContinuous( vector<int> numbers ) {
        //先排序
        sort(numbers.begin(), numbers.end()); 
        int zero = 0;
        int gap = 0;
        for(int i = 0; i < numbers.size() - 1; i++){ 
            //统计零牌数
            if(numbers[i] == 0) 
                zero++;
            else{
                //不可重复
                if(numbers[i + 1] - numbers[i] == 0) 
                    return false;
                else
                    //统计间隔数
                    gap += numbers[i + 1] - numbers[i] - 1; 
            }
        }
        //比较间隔与零牌数
        if(gap > zero)
            return false;
        else
            return true;
    }
};

Python实现代码：

class Solution:
    def IsContinuous(self , numbers: List[int]) -> bool:
        #先排序
        numbers = sorted(numbers); 
        zero = 0
        gap = 0
        for i in range(len(numbers) - 1):
            #统计零牌数
            if numbers[i] == 0: 
                zero += 1
            else:
                #不可重复
                if numbers[i + 1] - numbers[i] == 0: 
                    return False
                else:
                    #统计间隔数
                    gap += numbers[i + 1] - numbers[i] - 1 
        #比较间隔与零牌数
        if gap > zero:
            return False
        else:
            return True

复杂度分析：