Skip to content

Files

This branch is 634 commits behind doocs/leetcode:main.

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

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
May 29, 2024
Feb 6, 2023
Jan 13, 2024
Oct 31, 2023
Feb 6, 2023
Feb 6, 2023
Feb 6, 2023
Feb 7, 2022
May 29, 2024
Feb 7, 2022
comments difficulty edit_url
true
简单

题目描述

若干副扑克牌中随机抽 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 记录数字是否出现过,用 mimx 记录最大值和最小值。遍历数组,忽略大小王($0$),求出数组的最大、最小值。若最后差值超过 4 ,则无法构成顺子。

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

Python3

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

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