扑克牌中的顺子

关键词：set、贪心算法

题目描述

从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。

示例 1：

1 2	`输入: [1,2,3,4,5] 输出: True`

示例 2：

1 2	`输入: [0,0,1,2,5] 输出: True`

限制：

数组长度为 5

数组的数取值为 [0, 13] .

解法

解法一：

思路：

判重。序数牌一旦有重复就不能构成顺子;
找首尾。找到5张牌中除了0的Min和Max。然后在手牌中查找，如果这之间的牌有缺失，记一个int fail++，如果fail>kings（0的数量），返回false，否则返回true;
另外，题目说明了抽5张牌，所以自己构造的不是5张牌的测试点必定结果为false，不必考虑

算法流程：

初始化：伪头节点 dum ，节点 cur指向 dum 。
循环合并：当 l1 或 l2 为空时跳出；

当 l1.val<l2.val时： cur 的后继节点指定为 l1 ，并 l1向前走一步；

当 l1.val≥l2.val时： cur 的后继节点指定为 l2 ，并 l2向前走一步；

节点 cur向前走一步，即 cur=cur.next 。

合并剩余尾部：跳出时有两种情况，即 l1为空或 l2为空。
```
若 l1≠null： 将 l1 添加至节点 cur 之后；
否则： 将 l2 添加至节点 cur之后。
```
返回值：合并链表在伪头节点 dum 之后，因此返回 dum.next 即可。

代码：

class Solution {
public:
    bool isStraight(vector<int>& nums) {
        int kings=0, Min=13, Max=-1, fail=0;
        int n=nums.size();
        set<int> my;
        for(int i=0;i<n;++i){
            if(nums[i]==0){
                kings++;//记录大小王数量
            }
            else if(my.find(nums[i]) != my.end()) return false;//有重复
            else{
                Min=min(Min,nums[i]);
                Max=max(Max,nums[i]);
                my.insert(nums[i]);
            }
        }
        for(int i=Min;i<=Max;++i){
            if(my.find(i) == my.end()) fail++;//统计缺少的牌
        }
        if(fail>kings) return false;
        return true;
    }
};

解法二：

思路：

考虑0的个数能不能弥补空缺。（贪心算法）

代码：

class Solution {
public:
    bool isStraight(vector<int>& nums) {
        int cnt=count(nums.begin(),nums.end(),0);//统计0的个数
        sort(nums.begin(),nums.end());//排序
        bool judge=true;
        for(auto i=0;i<nums.size()-1;++i)
        {
            if(nums[i]==0)
                continue;
            else
            {
                //相邻两张牌相差小于0的数量且不相等
                if(nums[i+1] - nums[i] - 1 <= cnt && nums[i+1] - nums[i] > 0)
                    cnt -= nums[i+1]-nums[i]-1;//用0去弥补
                else 
                {
                    judge=false;
                    break;
                }
            }
        }
        return judge;
    }
};

知识点

set的使用
贪心算法