【细节】剑指offer——面试题44：扑克牌顺子

力扣，https://leetcode.cn/problems/bu-ke-pai-zhong-de-shun-zi-lcof/description/

Python

class Solution:
    def checkDynasty(self, places: List[int]) -> bool:
        zero_count, n = 0, len(places)
        places.sort()
        for i in range(n):
            if places[i] == 0:
                zero_count += 1
            elif i > 0 and places[i] == places[i-1]:
                return False
        return places[n-1] - places[zero_count] <= 4

法1

一直在想统计0的个数，然后判断相邻的数之间的差值，然后最后判断是否能抵消。
代码略显繁琐

class Solution {
    public boolean checkDynasty(int[] places) {
        int zeroCount = 0;
        List<Integer> noZeroList = new ArrayList<>();
        for (int val : places) {
            if (val == 0) {
                ++zeroCount;
            } else {
                noZeroList.add(val);
            }
        }
        
        Collections.sort(noZeroList); // 从小到大排序
        for (int i = 1; i < noZeroList.size(); ++i) {
            int diff = noZeroList.get(i) - noZeroList.get(i - 1) - 1;
            if (diff == -1) {
                return false;
            }
            if (diff == 0) {
                continue;
            }
            zeroCount -= diff;
            if (zeroCount < 0) {
                return false;
            }
        }

        return true;
    }
}

法2

非常简洁的方法！！！

class Solution {
    public boolean checkDynasty(int[] places) {
        Arrays.sort(places);
        int zeroCount = 0;
        for (int i = 0; i < places.length; ++i) {
            if (places[i] == 0) {
                ++zeroCount;
            } else if (i > 0 && places[i - 1] == places[i]) {
                return false;
            }
        }

        return places[4] - places[zeroCount] < 5;
    }
}

##Solution1:
20180907重做
书上的思路。

class Solution {
public:
    bool IsContinuous(vector<int> numbers) {
        if (numbers.size() < 5) return false;
        int Poker[14] = {0}, begin_index = 14, end_index = -1;
        for (auto i : numbers) {
            if (i) { //确定出非大小王牌的起止点
                begin_index = min(begin_index, i);
                end_index = max(end_index, i);
            }
            Poker[i]++;
            //若非大小王的牌出现次数大于1，直接return false
            if (i && Poker[i] > 1) return false;
        }
        //四张大小王也可以直接return true
        if (Poker[0] == 4) return true;
        int nums_0 = 0;
        for (int i = begin_index; i <= end_index; i++) {
            if (!Poker[i])
                nums_0++;
        }
        //当间隔之间的0数量小于大小王的数量则return true
        //否则，return false
        if (nums_0 > Poker[0])
            return false;
        else
            return true;
    }
};

思路关键：这副扑克共有56张

class Solution {
public:
    bool IsContinuous( vector<int> numbers ) { //此幅牌共56张，13*4 + 2 + 2 = 56
        set<int> kind_no_zero;
        int num_of_zero = 0;
        for(int i = 0; i != numbers.size(); i++) {
            if(numbers[i] == 0)
                num_of_zero++;
            else 
                kind_no_zero.insert(numbers[i]);
        }
        if(num_of_zero + kind_no_zero.size() != 5) //扑克牌中的非零数字有重复，则一定不是顺子
            return false;
        else if(kind_no_zero.size() == 1) //非零数只有一个，则肯定是顺子
            return true;
        else { //非零数>=2时
            int temp = *(--kind_no_zero.end()) - *kind_no_zero.begin(); //注意set的迭代器只能
            if( temp <= 4)                                       //自增自减，不能+n，-n
                return true;
            else 
                return false;
        }
    }
};