61. 扑克牌中的顺子

comments: true
difficulty: 简单
edit_url: https://github.com/doocs/leetcode/edit/main/lcof/%E9%9D%A2%E8%AF%95%E9%A2%9861.%20%E6%89%91%E5%85%8B%E7%89%8C%E4%B8%AD%E7%9A%84%E9%A1%BA%E5%AD%90/README.md

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

题目描述

从若干副扑克牌中随机抽 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] .

解法

方法一：遍历

我们首先明确顺子不成立的核心条件：

1. 存在非 $0$ 的重复。
2. 最大值与最小值的差距超过 4（最大最小值比较不包括 $0$ 在内）。

因此，我们可以用一个哈希表或数组 vis 记录数字是否出现过，用 mi 和 mx 记录最大值和最小值。遍历数组，忽略大小王（$0$），求出数组的最大、最小值。若最后差值超过 $4$，则无法构成顺子。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组长度。

Python3

class Solution:
    def isStraight(self, nums: List[int]) -> bool:
        if not numbers:return False
        vis = set()
        mi, mx = float('inf'), float('-inf')
        for x in nums:
            if x==0:continue #大小王可以看做任意数字
            if x in vis: # 非零的重复
                return False
            
            mi = min(mi, x)
            mx = max(mx, x)
            vis.add(x)
        return mx - mi <= 4 #最大值与最小值的差距是否超过4

Java

class Solution {
    public boolean isStraight(int[] nums) {
        boolean[] vis = new boolean[14];
        int mi = 20, mx = -1;
        for (int x : nums) {
            if (x == 0) {
                continue;
            }
            if (vis[x]) {
                return false;
            }
            vis[x] = true;
            mi = Math.min(mi, x);
            mx = Math.max(mx, x);
        }
        return mx - mi <= 4;
    }
}

C++

class Solution {
public:
    bool isStraight(vector<int>& nums) {
        bool vis[14]{};
        int mi = 20, mx = -1;
        for (int& x : nums) {
            if (x == 0) {
                continue;
            }
            if (vis[x]) {
                return false;
            }
            vis[x] = true;
            mi = min(mi, x);
            mx = max(mx, x);
        }
        return mx - mi <= 4;
    }
};

Go

func isStraight(nums []int) bool {
	vis := map[int]bool{}
	mi, mx := 20, -1
	for _, x := range nums {
		if x == 0 {
			continue
		}
		if vis[x] {
			return false
		}
		vis[x] = true
		mi = min(mi, x)
		mx = max(mx, x)
	}
	return mx-mi <= 4
}

TypeScript

function isStraight(nums: number[]): boolean {
    nums.sort((a, b) => a - b);
    let j = 0;
    for (let i = 0; i < 4; i++) {
        if (nums[i] === 0) {
            j++;
        } else if (nums[i] === nums[i + 1]) {
            return false;
        }
    }
    return nums[4] - nums[j] <= 4;
}

Rust

impl Solution {
    pub fn is_straight(mut nums: Vec<i32>) -> bool {
        nums.sort();
        let mut j = 0;
        for i in 0..4 {
            if nums[i] == 0 {
                j += 1;
            } else if nums[i] == nums[i + 1] {
                return false;
            }
        }
        nums[4] - nums[j] <= 4
    }
}

JavaScript

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var isStraight = function (nums) {
    const vis = new Array(14).fill(false);
    let mi = 20;
    let mx = -1;
    for (const x of nums) {
        if (x == 0) {
            continue;
        }
        if (vis[x]) {
            return false;
        }
        vis[x] = true;
        mi = Math.min(mi, x);
        mx = Math.max(mx, x);
    }
    return mx - mi <= 4;
};

C#

public class Solution {
    public bool IsStraight(int[] nums) {
        bool[] vis = new bool[14];
        int mi = 20, mx = -1;
        foreach(int x in nums) {
            if (x == 0) {
                continue;
            }
            if (vis[x]) {
                return false;
            }
            vis[x] = true;
            mi = Math.Min(mi, x);
            mx = Math.Max(mx, x);
        }
        return mx - mi <= 4;
    }
}

Swift

class Solution {
    func isStraight(_ nums: [Int]) -> Bool {
        var vis = Array(repeating: false, count: 14)
        var mi = 20, mx = -1
        for x in nums {
            if x == 0 {
                continue
            }
            if vis[x] {
                return false
            }
            vis[x] = true
            mi = min(mi, x)
            mx = max(mx, x)
        }
        return mx - mi <= 4
    }
}