【劍指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 + 周遊