【数学专题】剑指 Offer 61. 扑克牌中的顺子-跟着帅地玩副业，开拓第二曲线PlayOffer

lQl 永久会员 2024年12月22日上午12:30

时间空间复杂度O(1)

class Solution {
    public boolean checkDynasty(int[] places) {
        int min = 14;
        int max = 0;
        HashSet<Integer> map = new HashSet<>();
        for (int place : places) {

            if (place == 0)
                continue;
            else {
                if (map.contains(place))
                    return false;
                else
                    map.add(place);
                if (place < min)
                    min = place;
                if (place > max)
                    max = place;
            }
        }
        if ((max - min) <= 4)
            return true;
        else
            return false;
    }
}

0 赞同 0 条回复

陆狗陆狗普通 2024年12月16日下午10:21

解题思路
– 能组成连续序列的数组应当满足2个条件
– 1、里面的任一元素不能重复（除了0）
– 2、最大值和最小值不能超过4（除了0）
【题解1】排序+遍历（未完全利用好排序特性的）

class Solution {
    public boolean checkDynasty(int[] places) {
        // 1、不能重复（除了0）
        // 2、最大值和最小值不能超过4（除了0）
        // 先排序+再遍历
        Arrays.sort(places);
        int min = 0;
        int max = 0;
        for (int i = 0; i < places.length; i++) {
            if (places[i] != 0) {
                // 找到第一个不为0的
                if (min == 0 || max == 0) {
                    min = places[i];
                    max = places[i];
                }
                // 不能重复(必须排序后才好比较)
                if (i < places.length - 1 && places[i] == places[i + 1]) {
                    return false;
                }
                min = Math.min(places[i], min);
                max = Math.max(places[i], max);
                // 最大值和最小值不能超过4（除了0）
                if (max - min >= 5) {
                    return false;
                }
            }
        }
        return true;
    }
}

【题解2】排序+遍历（完全利用好排序特性的）

class Solution {
    public boolean checkDynasty(int[] places) {
        // 1、不能重复（除了0）
        // 2、最大值和最小值不能超过4（除了0）
        // 先排序+再遍历
        Arrays.sort(places);
        int zeroCount = 0;
        // 遍历到第4位即可
        for (int i = 0; i < places.length - 1; i++) {
            if (places[i] == 0) {
                // 利用排序后从小到大的特性
                zeroCount++;
            } else {
                // 不能重复(必须排序后才好比较)，因为遍历到i < places.length-1，所以不用判断边界问题
                if (places[i] == places[i + 1]) {
                    return false;
                }

            }
        }
        // 利用排序特性
        // places[zeroCount] 一定是最小值
        // (places[places.length -1] 一定是最大值
        if (places[places.length - 1] - places[zeroCount] >= 5) {
            return false;
        }
        return true;
    }
}

【题解3】用Hash表存数字用于判断重复性，用min和max来比较极限大小

class Solution {
    public boolean checkDynasty(int[] places) {
        // 1、不能重复（除了0）
        // 2、最大值和最小值不能超过4（除了0）
        // 使用Set来存储数据判断是否重复，使用min和max来存储最大和最小值
        Set<Integer> set = new HashSet();
        int min = 0;
        int max = 0;
        for (int i = 0; i < places.length; i++) {
            int current = places[i];
            if (current == 0) {
                continue;
            }
            if (set.contains(current)) {
                return false;
            }
            set.add(current);
            if (min == 0 || max == 0) {
                // 第一次需要进行赋值
                min = current;
                max = current;
            } else {
                min = Math.min(min, current);
                max = Math.max(max, current);
            }
        }
        return max - min <= 4;
    }
}

0 赞同 0 条回复

Xiang. 永久会员 2024年12月16日下午1:01

class Solution {
    //思路:通过排序规律：①max-min<5 ②不重复 ③0为特殊情况，直接跳过
    public boolean checkDynasty(int[] places) {
        Set<Integer> arrSet=new HashSet<>();
        int max=0;
        int min=14;
        for(int i=0;i<places.length;i++){
            if(places[i]==0) continue;
            if(arrSet.contains(places[i])) return false;
            arrSet.add(places[i]);
            max=Math.max(places[i],max);
            min=Math.min(places[i],min);
        }
        return max-min<5;
    }
}
时间空间复杂度均为：O（1）

0 赞同 0 条回复

Aatorx 永久会员 2024年12月13日下午3:24

class Solution {
public:
    bool checkDynasty(vector<int>& places) {
        sort(places.begin(), places.end());
        int n = 0;
        for (int i = 0; i < places.size(); i++) {
            if (places[i] == 0) {
                n++;
            }
            else if (places[i] == places[i+1]) {
                return false;
            }
        }
        return places[4] - places[n] < 5;
    }
};

排序后统计第一个不为零的元素与最大元素的差值，若小于5，则为顺子。
时间复杂度O(Nlogn)，空间复杂度O(1)。

0 赞同 0 条回复

晓宇普通 2024年12月13日下午12:00

class Solution {
public:
    bool checkDynasty(vector<int>& places) {
        // 集合
        // 不存在0以外的重复数
        // 最大值 - 最小值 < 5
        set<int>  ns;
        for(int i = 0; i < places.size();i ++){
            if(places[i] == 0) continue;
            if(ns.find(places[i]) != ns.end()) return false;
            else ns.insert(places[i]);
        }
        // 判断最大值和最小值的差是否小于 5

        return (*ns.rbegin()) - (*ns.begin()) < 5;    
    }
    // o(nlogn)集合查找和插入 o(n)
};

class Solution {
public:
    bool checkDynasty(vector<int>& places) {
        // 排序
        int idx = 0;  // 标记除0外的最小位
        int len = places.size();
        sort(places.begin(),places.end());
        if(places[len - 1] == 0) return true;  // 特殊情况：五个0
        // 排除重复元素
        for(int i = 0;i < len - 1;i ++){
            if(places[i] == 0) {
                idx = i + 1;
                continue;
            }
            else if(places[i] == places[i + 1]) return false; // 排除除0外的重复项
        }

        return places[len - 1] - places[idx] < 5;
        return true;
    }
    // o(nlogn)排序 o(1)
};

0 赞同 0 条回复

月下足迹普通 2024年12月13日上午11:20

class Solution {
public boolean checkDynasty(int[] places) {
Set repeat = new HashSet<>();
int max = 0, min = 14;
for(int place : places) {
if(place 0) continue; // 跳过未知朝代
max = Math.max(max, place); // 最大编号朝代
min = Math.min(min, place); // 最小编号朝代
if(repeat.contains(place)) return false; // 若有重复，提前返回 false
repeat.add(place); // 添加此朝代至 Set
}
return max – min < 5; // 最大编号朝代 – 最小编号朝代 < 5 则连续

}

0 赞同 0 条回复

Kisara 普通 2024年12月13日上午12:00

实现两个条件
1.无重复元素
2.最大朝代-最小朝代<5

class Solution {
    public boolean checkDynasty(int[] places) {
        Set<Integer> set=new HashSet<>();
        int max=0;
        int min=14;
        for(int n:places){
            if(n==0) continue;
            max=Math.max(n,max);
            min=Math.min(n,min);
            if(set.contains(n)) return false;
            set.add(n);
        }
        if(max-min<5) return true;
        else return false;
    }
}

O1 O1

0 赞同 0 条回复

迢迢星野普通 2024年12月12日下午9:38

class Solution {

    /**
     * 展览馆展出来自 13 个朝代的文物，每排展柜展出 5 个文物。某排文物的摆放情况记录于数组 places，其中 places[i] 表示处于第 i 位文物
     * 的所属朝代编号。其中，编号为 0 的朝代表示未知朝代。请判断并返回这排文物的所属朝代编号是否能够视为连续的五个朝代（如遇未知朝代
     * 可算作连续情况）。
     * 
     * 题意解读：连续的五个朝代，说明这一排的文物 max - min < 5 即可，且无重复，去掉 0
     * 方法一：哈希 + 记录最大和最小值
     * 方法二：排序 + 记录最大和最小值
     * @param places
     * @return
     */
    public boolean checkDynasty(int[] places) {
        Set<Integer> set = new HashSet<>();
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for (int place : places) {
            // 跳过未知朝代
            if (place == 0) {
                continue;
            }
            // 如果出现重复朝代，返回 false 
            if (set.contains(place)) {
                return false;
            }
            min = Math.min(min, place);
            max = Math.max(max, place);
            set.add(place);
        }
        return max - min < 5;
    }

    public boolean checkDynasty2(int[] places) {
        Arrays.sort(places);
        int unknown = 0;
        for (int i = 0; i < 4; i++) {
            if (places[i] == 0) {
                unknown++;
            }else if (places[i] == places[unknown]) {
                // 出现重复朝代，返回 false
                return false;
            }
        }
        return places[4] - places[unknown] < 5;
    }
}

思路：连续的五个朝代，说明这一排的文物无重复，去掉 0 后，max - min < 5 即可。
时间复杂度：O(n) | O(n)
空间复杂度：O(n) | O(1)

0 赞同 0 条回复

jaron 普通 2024年12月12日下午9:27

class Solution {
    public boolean checkDynasty(int[] places) {
        HashSet<Integer> set = new HashSet<>();
        int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
        for (int a : places) {
            // 不能重复
            if (a == 0)
                continue;
            if (set.contains(a))
                return false;
            set.add(a);
            max = Math.max(a, max);
            min = Math.min(a, min);
        }
        // 最大最小值差值小于5
        return max - min < 5;
    }
}

0 赞同 0 条回复

【数学专题】剑指 Offer 61. 扑克牌中的顺子

共以下 9 个回答

# 回答此问题取消回复

【数学专题】剑指 Offer 61. 扑克牌中的顺子

共以下 9 个回答

# 回答此问题 取消回复

# 回答此问题取消回复