【剑指Offer】个人学习笔记_61_扑克牌中的顺子

- 题目：
- - - [剑指 Offer 61. 扑克牌中的顺子](https://leetcode-cn.com/problems/bu-ke-pai-zhong-de-shun-zi-lcof/)
    - 题目分析
- 初始解答：
- 学习他人：
- - 方法一:
  - 方法二：
  - 方法三：
  - 方法四：
  - 方法五：
  - - 方法一：集合 Set + 遍历
    - 方法二：排序 + 遍历
- 总结

刷题日期：下午8:33 2021年5月25日星期二

个人刷题记录，代码收集，来源皆为leetcode

经过多方讨论和请教，现在打算往Java方向发力

主要答题语言为Java

题目：

剑指 Offer 61. 扑克牌中的顺子

难度简单131

从扑克牌中随机抽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，够不够补差下的位数的问题。

数组长度也唯一，目前从例子中并不能看出是不是所有的输入都是递增序列。

分情况讨论。

不设置5个flag的话，就得确定全部递增才能满足条件。

初始解答：

暴力，相当的暴力。

class Solution {
    public boolean isStraight(int[] nums) {
        //默认nums满足递增
        Arrays.sort(nums);
        //首先不考虑0的情况，那么必须是递增序列。
        if(nums[4] - nums[0] == 4) {
            for (int i = 1; i < nums.length; i++) {//有对肯定不是
                if(nums[i] == nums[i-1] && nums[i] != 0) return false;
            }
            return true;
        }
        //一个0
        if(nums[0] == 0 && nums[1] != 0 && (nums[4] - nums[1] <= 4)) {
            for (int i = 1; i < nums.length; i++) {//有对肯定不是
                if(nums[i] == nums[i-1] && nums[i] != 0) return false;
            }
            return true;
        } 
        //两个0
        if(nums[0] == 0 && nums[1] == 0 && (nums[4] - nums[2] <= 4)) {
            for (int i = 1; i < nums.length; i++) {//有对肯定不是
                if(nums[i] == nums[i-1] && nums[i] != 0) return false;
            }
            return true;
        }
        if(nums[0] == 0 && nums[1] == 0 && nums[2] == 0 &&(nums[4] - nums[3] <= 4)) {
                        for (int i = 1; i < nums.length; i++) {//有对肯定不是
                if(nums[i] == nums[i-1] && nums[i] != 0) return false;
            }
            return true;
        }
        return false;
    }
}

就问问还有谁

提交结果	执行用时	内存消耗	语言	提交时间	备注
通过	1 ms	35.4 MB	Java	2021/05/25 21:05	添加备注
解答错误	N/A	N/A	Java	2021/05/25 21:02	添加备注
解答错误	N/A	N/A	Java	2021/05/25 21:00	添加备注
解答错误	N/A	N/A	Java	2021/05/25 20:59	添加备注
解答错误	N/A	N/A	Java	2021/05/25 20:58	添加备注
解答错误	N/A	N/A	Java	2021/05/25 20:57	添加备注
解答错误	N/A	N/A	Java	2021/05/25 20:56	添加备注
编译出错	N/A	N/A	Java	2021/05/25 20:56	添加备注
解答错误	N/A	N/A	Java	2021/05/25 20:53	添加备注
解答错误	N/A	N/A	Java	2021/05/25 20:52	添加备注

执行结果：通过

显示详情添加备注

执行用时：1 ms, 在所有 Java 提交中击败了91.53%的用户

内存消耗：35.4 MB, 在所有 Java 提交中击败了99.18%的用户

改进后的代码

class Solution {
    public boolean isStraight(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 1; i++){
            if(nums[i] == nums[i + 1] && nums[i] != 0) return false; //有重复且不为0的，错误
        }
        if(nums[4] - nums[0] == 4) return true; //默认nums满足递增
        if(nums[0] == 0 && nums[1] != 0 && (nums[4] - nums[1] <= 4)) return true;//一个0
        if(nums[0] == 0 && nums[1] == 0 && (nums[4] - nums[2] <= 4)) return true;//两个0
        if(nums[0] == 0 && nums[1] == 0 && nums[2] == 0 &&(nums[4] - nums[3] <= 4)) return true;//三个0，就离谱
        return false;
    }
}

执行结果：通过

显示详情添加备注

执行用时：1 ms, 在所有 Java 提交中击败了91.53%的用户

内存消耗：35.6 MB, 在所有 Java 提交中击败了93.56%的用户

K神还是牛

class Solution {
    public boolean isStraight(int[] nums) {
        Arrays.sort(nums);
        int joker = 0; //大小王
        for(int i = 0; i < 4; i++) {
            if(nums[i] == 0) joker++;
            else if(nums[i] == nums[i + 1]) return false; //出现对了
        }
        return nums[4] - nums[joker] < 5;// 最大牌 - 最小牌 < 5 则可构成顺子
    }
}

执行结果：通过

显示详情添加备注

执行用时：1 ms, 在所有 Java 提交中击败了91.53%的用户

内存消耗：35.9 MB, 在所有 Java 提交中击败了33.85%的用户

学习他人：

方法一:

梦小冷L1 （编辑过）2020-03-04

其实我第一眼看这题懵逼了，因为我不玩牌，不知道啥叫顺子，哭。后来看了别人的解答，觉得简单的理解就是，这个数组中0可以当任何数用，所以当牌不连续的时候，它就可以替补一下，进而达到顺的要求。举个例子 0 0 1 2 4 5 6,这个数组中，0有两个，所以我们有俩万能替补，接着我们可以发现2-4之间不连续，缺个3，这样我们就可以把一个0放到哪里当三，0 1 2 0 4 5 6,0代替了3的位置，达到了连续的要求，那啥时候就不行了呢，当你万能替补0的个数·，没有间隙大的时候，比如你只有一个·0，但是其中数组中有俩连续的数之间差特别大，达到0的个数不够，比如1-7，中间差了5个数，你就一个0显然不够，所以这就不是顺儿。哎，以后应该多玩玩牌

class Solution {
    public boolean isStraight(int[] nums) {
        Arrays.sort(nums);
        int zeroCnt=0,diff=0;
        for(int i=0;i<nums.length-1;i++){
            if(nums[i]==0){
                zeroCnt++;
            }else{
                if(nums[i]==nums[i+1]) return false;
                if(nums[i]+1!=nums[i+1]){
                    diff+=nums[i+1]-nums[i]-1;
                }
            }
        }
        return zeroCnt>=diff;
    }
}

方法二：

ResolmiL3 （编辑过）2020-03-02

只有5张牌，先排除对子，然后求最大和最小的牌面之差就行了，小于等于4就肯定是顺子

public boolean isStraight(int[] nums) {
    int[] bucket=new int[14];
    int min=14,max=-1;
    for(int i=0;i<nums.length;i++){
        if(nums[i]==0) continue;
        //有非0的对子,直接false
        if(bucket[nums[i]]==1) return false;
        bucket[nums[i]]++;
        //记录牌面最大和最小
        min=Math.min(min,nums[i]);
        max=Math.max(max,nums[i]);
    }
    //小于等于4就行,少的用0补
    return max-min<=4;
}

方法三：

唐東L1 6 小时前

class Solution {
    public boolean isStraight(int[] nums) {
        Arrays.sort(nums);
        int count = 0;  //记录0的个数
        for(int i = 0,j = 1;j < nums.length;i++,j++){
            if(nums[i] == 0){
                count++;
            }else{
                if(nums[j] == nums[i])  return false;
                if(nums[j] - nums[i] == 1)  continue;
                else count -= nums[j] - nums[i] - 1;
                if(count < 0)   return false;
            }
        }
        return true;
    }
}

方法四：

Jupiter 2021-04-28 java 1ms

public boolean isStraight(int[] nums) {
        Arrays.sort(nums);
        int count = 0;// record the number of zero
       for(int i = 0; i < 4; i ++){
           if(nums[i] == 0) count ++;
           else{
               if(nums[i + 1] - nums[i] > count + 1 || nums[i + 1] == nums[i]){
                   return false;
               }
           }
       }
        return true;
    }

方法五：

K神解题思路：

【剑指Offer】个人学习笔记_61_扑克牌中的顺子

作者：jyd

链接：https://leetcode-cn.com/problems/bu-ke-pai-zhong-de-shun-zi-lcof/solution/mian-shi-ti-61-bu-ke-pai-zhong-de-shun-zi-ji-he-se/

来源：力扣（LeetCode）

方法一：集合 Set + 遍历

遍历五张牌，遇到大小王（即 0 ）直接跳过。

判别重复：利用 Set 实现遍历判重， Set 的查找方法的时间复杂度为O(1) ；

获取最大 / 最小的牌：借助辅助变量 ma 和 mi ，遍历统计即可。

class Solution {
    public boolean isStraight(int[] nums) {
        Set<Integer> repeat = new HashSet<>();
        int max = 0, min = 14;
        for(int num : nums) {
            if(num == 0) continue; // 跳过大小王
            max = Math.max(max, num); // 最大牌
            min = Math.min(min, num); // 最小牌
            if(repeat.contains(num)) return false; // 若有重复，提前返回 false
            repeat.add(num); // 添加此牌至 Set
        }
        return max - min < 5; // 最大牌 - 最小牌 < 5 则可构成顺子
    }
}

方法二：排序 + 遍历

class Solution {
    public boolean isStraight(int[] nums) {
        int joker = 0;
        Arrays.sort(nums); // 数组排序
        for(int i = 0; i < 4; i++) {
            if(nums[i] == 0) joker++; // 统计大小王数量
            else if(nums[i] == nums[i + 1]) return false; // 若有重复，提前返回 false
        }
        return nums[4] - nums[joker] < 5; // 最大牌 - 最小牌 < 5 则可构成顺子
    }
}

K神还是牛啊，一样的思路写出来就更直观更简单

总结

以上就是本题的内容和学习过程了，难得自己分析出来双90多的解答，奖励自己早下班哈哈。

欢迎讨论，共同进步。

【剑指Offer】个人学习笔记_61_扑克牌中的顺子

目录

题目：

剑指 Offer 61. 扑克牌中的顺子

题目分析

初始解答：

学习他人：

方法一:

方法二：

方法三：

方法四：

方法五：

方法一：集合 Set + 遍历

方法二：排序 + 遍历

总结

继续阅读

neo4j之cypher使用文档

Dijkstra--简易版（最短路径）

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

spark/scala关于【资源文件】加载方法概述外部文件加载方案测试资源文件打包入jar包中小结

mybatis_入门程序Mybatis入门

AOP编程_Android优雅权限框架(1)概念基础，2021金三银四前言正文大纲正文

LeetCode OJ Binary Tree Right Side View

Effective Java 8:通用程序设计

leetcode809

OOM三种类型

工厂模式-三种类型

【递归】高效率求2的n次幂

win10本地scala和spark安装安装scala安装spark

Linux设备模型（中）之上层容器

scala (3) Function 和 Method

hdu7108哈希

【剑指Offer】个人学习笔记_61_扑克牌中的顺子

目录

题目：

剑指 Offer 61. 扑克牌中的顺子

题目分析

初始解答：

学习他人：

方法一:

方法二：

方法三：

方法四：

方法五：

方法一： 集合 Set + 遍历

方法二：排序 + 遍历

总结

继续阅读

方法一：集合 Set + 遍历