面试题61. 扑克牌中的顺子¶

面试题61. 扑克牌中的顺子¶

Tags: Easy Array

Links: https://leetcode-cn.com/problems/bu-ke-pai-zhong-de-shun-zi-lcof/

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

示例 1:

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

示例 2:

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

限制：

数组长度为 5

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

class Solution {
public:
    bool isStraight(vector<int>& nums) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = nums.size();
        vector<bool> used(14, false);
        int maxValue = 1, minValue = 14;
        for (auto e : nums) {
            if (e == 0) continue;
            if (used[e]) return false;
            used[e] = true;
            maxValue = max(e, maxValue);
            minValue = min(e, minValue);
        }

        return maxValue - minValue + 1 <= 5;
    }
};

执行用时 :0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗 :10.2 MB, 在所有 C++ 提交中击败了100.00%的用户

不妨先思考一个这样的问题：有一串连续的数字（无重复），这串数字中最大值为 m，最小值为 n ，问你这串数字中一共有多少个数字？

答案：m - n + 1

同样，如果我们能够知道 5 张扑克牌中的最大值 maxValue 和最小值 minValue，那我们就知道，要使它为顺子需要 maxValue - minValue + 1 张牌。

在查找 maxValue 和 minValue 过程中，跳过大小王 0 。如果 maxValue - minValue + 1 > 5，说明题目给的 5 张牌不足以构成顺子，返回 false . 即使里面有大小王，也不够用来填补使它构成顺子。如果 maxValue - minValue + 1 <= 5，说明 5 张牌足以构成顺子，返回 true。里面的大小王填补在合适位置即可。同时，我们再定义一个标志数组判断是否有重复数字，发现重复数字直接返回 false 即可。