面试题 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] .

解法

方法一：遍历

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

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

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

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

Python3JavaC++GoTypeScriptRustJavaScriptC#Swift

class Solution:
    def isStraight(self, nums: List[int]) -> bool:
        vis = set()
        mi, mx = inf, -inf
        for x in nums:
            if x == 0:
                continue
            if x in vis:
                return False
            vis.add(x)
            mi = min(mi, x)
            mx = max(mx, x)
        return mx - mi <= 4

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;
    }
}

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;
    }
};

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
}

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;
}

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
    }
}

/**
 * @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;
};

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;
    }
}

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
    }
}

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

题目描述

解法

方法一：遍历

评论