微信公众号:路人zhang
扫码关注微信公众号

回复“面试手册”,获取本站PDF版

回复“简历”,获取高质量简历模板

回复“加群”,加入程序员交流群

回复“电子书”,获取程序员类电子书

当前位置: 算法 > 剑指offer > 剑指offer 61. 扑克牌中的顺子
本文链接:https://www.mianshi.online/2806.html

题目描述

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


题解

(模拟,排序) O(nlogn)

  1. 先将数组排序
  2. 把 0 先过滤掉,找到第一个不为 0 的位置 k
  3. 遍历数组,如果有重复元素,肯定不能构成顺子
  4. 如果最后一个元素和第一个非 0 元素之差大于 4 nums.back() - nums[k] + 1 > 5 不能构成顺子,否则就是顺子

时间复杂度

数组排序的时间复杂度为 O(nlogn)

空间复杂度

O(1)

C++ 代码

class Solution {
public:
    bool isStraight(vector<int>& nums) {
        if (nums.empty()) return false;
        sort(nums.begin(), nums.end());

        int k = 0;
        while (!nums[k]) k ++ ;

        for (int i = k + 1; i < nums.size(); i ++ )
            if (nums[i - 1] == nums[i])
                return false;
        return nums.back() - nums[k] < 5;
    }
};

Java 代码

import java.util.Arrays;

class Solution {
    public boolean isStraight(int[] nums) {
        if (nums == null || nums.length == 0) {
            return false;
        }

        Arrays.sort(nums);
        int k = 0;
        while (nums[k] == 0) {
            k ++ ;
        }

        for (int i = k + 1; i < nums.length; i ++ ) {
            if (nums[i - 1] == nums[i]) {
                return false;
            }
        }

        return nums[nums.length - 1] - nums[k] < 5;
    }
}

Python 代码

class Solution:
    def isStraight(self, nums: List[int]) -> bool:
        if not nums:
            return False
        
        nums.sort()
        k = 0
        while not nums[k]:
            k += 1
        
        for i in range(k + 1, len(nums)):
            if nums[i - 1] == nums[i]:
                return False
        
        return nums[-1] - nums[k] < 5

本文由读者提供Github地址:https://github.com/tonngw


点击面试手册,获取本站面试手册PDF完整版