61.扑克牌中的顺子

参考链接

剑指offer_在线编程_牛客网

剑指 Offer 61. 扑克牌中的顺子-跟着帅地玩转校招，刷爆各类算法题帅地玩Offer

LCR 186. 文物朝代判断 - 力扣（LeetCode）

个人尝试

先把数组的元素排好序，再从不为‘0’的数字开始遍历数组，倘若不连续看能否使用‘0’来填补

class Solution {
    public boolean checkDynasty(int[] places) {
        // 排序
        if (places == null || places.length == 0) return false;
        sort(places, 0, places.length - 1);
        int i = 0;
        // 跳过 ‘0’
        while (places[i] == 0) i++;
        // 从第二个不为‘0’的数开始遍历
        int j = i + 1;
        int tmp = 0;
        while (j < places.length) {
            // 重复，跳出
            if (places[j] == places[j - 1]) break;
            // 与前一个数 / 或者 tmp 对比
            if (places[j] == places[j - 1] + 1 || places[j] == tmp - 1) j++;
            // 使用 tmp 填补缺少的连续数字
            else if (places[j] <= places[j - 1] + i + 1) {
                tmp = places[j] - 1;
                i = i - (places[j] - places[j - 1]);
                j++;
            } else {
                break;
            }
        }
        // 倘若遍历到数组末尾则证明符合连续规则
        return (j == places.length);
    }
    // 快排
    public void sort(int[] places, int start, int end) {
        if (start >= end) return;
        int i = start, j = end;
        int tmp = places[start];
        while (i < j) {
            while (j > i && places[j] >= tmp) j--;
            places[i] = places[j];
            while (i < j && places[i] <= tmp) i++;
            places[j] = places[i];
        }
        places[i] = tmp;
        sort(places, start, i - 1);
        sort(places, j + 1, end);
    }
}

优秀题解

class Solution {
    public boolean checkDynasty(int[] places) {
        int unknown = 0;
        Arrays.sort(places); // 数组排序
        for(int i = 0; i < 4; i++) {
            if(places[i] == 0) unknown++; // 统计未知朝代数量
            else if(places[i] == places[i + 1]) return false; // 若有重复，提前返回 false
        }
        return places[4] - places[unknown] < 5; // 最大编号朝代 - 最小编号朝代 < 5 则连续
    }
}

作者：Krahets
链接：https://leetcode.cn/problems/bu-ke-pai-zhong-de-shun-zi-lcof/solutions/212071/mian-shi-ti-61-bu-ke-pai-zhong-de-shun-zi-ji-he-se/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。