參考資料：力扣K神的講解

劍指 Offer 61. 撲克牌中的順子
簡(jiǎn)單
351
相關(guān)企業(yè)
從若干副撲克牌中隨機(jī)抽 5 張牌，判斷是不是一個(gè)順子，即這5張牌是不是連續(xù)的。2～10為數(shù)字本身，A為1，J為11，Q為12，K為13，而大、小王為 0 ，可以看成任意數(shù)字。A 不能視為 14。

示例 1:

輸入: [1,2,3,4,5]
輸出: True

示例 2:

輸入: [0,0,1,2,5]
輸出: True

限制：

數(shù)組長(zhǎng)度為 5

數(shù)組的數(shù)取值為 [0, 13] .

思路：
注意到 ‘0’（即大王、小王）的出現(xiàn)次數(shù)只有三種情況：

1. ‘0’不出現(xiàn)
   此時(shí)，可行數(shù)組（順子）的最大值與最小值之差 為 4
2. ‘0‘出現(xiàn)一次
   此時(shí)，可行數(shù)組（順子）的最大值與最小值之差 <= 4
3. ’0‘出現(xiàn)兩次
   此時(shí)，可行數(shù)組（順子）的最大值與最小值之差 <= 4
   所以，順子應(yīng)該滿足“除了0之外，最大值與最小值之差 < 5”這個(gè)數(shù)學(xué)規(guī)律。
   此外，常識(shí)告訴我們：順子不該有重復(fù)值。
   綜上，
   檢查 數(shù)組是否可行（順子）等價(jià)于
   檢查 “除了0之外，最大值與最小值之差 < 5” 和 ”無重復(fù)值“ 這兩個(gè)條件是否同時(shí)滿足。

解法一：集合+找最大值和最小值

使用集合檢查數(shù)組中是否有重復(fù)值；

  public boolean isStraight(int[] nums) {
        Set<Integer> repeat = new HashSet<>();
       
        int min=14;
        int max=0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]==0){                
                continue;
            }
            min = Math.min(nums[i],min);
            max=Math.max(nums[i],max);

            if(repeat.contains(nums[i])){
                return false;
            }
            repeat.add(nums[i]);

        }
        return max-min<5;
    }

解法二：排序+記錄0的個(gè)數(shù)

 public boolean isStraight2(int[] nums) {
      
        Arrays.sort(nums);
        int count0=0;
        for(int i=0;i<nums.length-1;i++){
            if(nums[i]==0) {
                count0++;
                continue;
            }
            if(nums[i]==nums[i+1]) return false;// Repeat!!
    
        }
        // 遍歷完成后，count0 就是 數(shù)組最小值所在位置
        return nums[4]-nums[count0]<5;
    }

解法三：排序+記錄0的個(gè)數(shù)+記錄空缺數(shù)字的個(gè)數(shù)（自己寫的つ﹏?）

我沒有觀察出來那個(gè)數(shù)學(xué)規(guī)律……
這個(gè)解法的思路很樸素。
首先排序，然后遍歷數(shù)組，數(shù)一下有多少”0“（作為救命稻草），有多少”缺失值“（作為坑）；
遍歷結(jié)束之后，看看 這些救命稻草 夠不夠 填補(bǔ)這些坑。文章來源地址http://www.zghlxwxcb.cn/news/detail-647206.html

 public boolean isStraight1(int[] nums) {
        Arrays.sort(nums);
        int count0=0;// count 0
        int cnt=0;// count all the missing values
        for(int i=0;i<5-1;i++){
            if(nums[i]==0){
                 count0++;
            }else{
                if(nums[i]==nums[i+1]-1){
                    continue;
                }
                if(nums[i]==nums[i+1]) return false;// repeat! 
    
                cnt+=nums[i+1]-nums[i]-1;
                // say, [2,3],nums[i+1]-nums[i]-1=3-2-1=0, means no missing value bwt 2 and 3
                // say, [4,6], nums[i+1]-nums[i]=6-4-1=1, means there exists one missing value bwt 4 and 6
            }

        }
        return count0>=cnt;// check if all available 0 could satisfy the demand of all missing values 

    }

到了這里，關(guān)于劍指 Offer ! 61. 撲克牌中的順子的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！