之前发过一篇,感觉还有深挖的地方,于是又补充一些信息
这题目虽然是middle难度题目,要解答出来是只要easy的时间,但是深挖可以有hard的难度

题解1 可以帮助复习线段树的使用,题解2 可以复习一下java基础知识

题解1 线段树

这是自己憋出来的线段树
在这里插入图片描述

  class SeatManager {
        public SeatManager(int n) {  // 假设座位都是0 如果坐了人就设置为1 如果返回座位就减去1  需要找到靠左边的最小值。
            int length = n + 1;
            right = n;
            arr = new int[length];
            minArr = new int[length * 4];
        }

        int[] arr;
        int[] minArr;
        int left = 1;
        int right;
        int root = 1;

        public int reserve() {
            int res = getMin();
            update(res, 1);
            return res;
        }

        public void unreserve(int seatNumber) {
            update(seatNumber, -1);
        }

        public int getMin() {
            return getMin(left, right, root);
        }

        public int getMin(int left, int right, int node) {
            if (left == right) {
                return left;
            }
            int mid = (left + right) / 2;
            int res;
            if (minArr[node * 2] == 0) {  // 只要左边的最小值还是0,那么需要的点必然还在左边
                res = getMin(left, mid, node * 2);
            } else {
                res = getMin(mid + 1, right, node * 2 + 1);
            }
            return res;
        }

        public void update(int index, int value) {
            update(index, value, left, right, root);
        }

        public void update(int index, int value, int left, int right, int node) {
            if (left == right) {
                // 更新值
                arr[left] += value;
                minArr[node] = arr[left];
                return;
            }
            // 这里需要对arr进行更新操作
            int mid = (left + right) / 2;
            if (index <= mid) {
                update(index, value, left, mid, node * 2);
            }
            if (index > mid) {
                update(index, value, mid + 1, right, node * 2 + 1);
            }
            minArr[node] = Math.min(minArr[node * 2], minArr[node * 2 + 1]);
        }
    }

这里是抄别人思路憋出来的线段树
在这里插入图片描述


 class SeatManager {
        public SeatManager(int n) {
            int length = n + 1;
            right = n;
            hasSeatArr = new int[length * 4]; // 先假设1,都是有座位的
            Arrays.fill(hasSeatArr, 1);
        }

        int[] hasSeatArr;
        int left = 1;
        int right;
        int root = 1;

        public int reserve() {
            int res = getMin();
            update(res, 0);
            return res;
        }

        public void unreserve(int seatNumber) {
            update(seatNumber, 1);
        }

        public int getMin() {
            return getMin(left, right, root);
        }

        public int getMin(int left, int right, int node) {
            if (left == right) {
                return left;
            }
            int mid = (left + right) / 2;
            int res;
            if (hasSeatArr[node * 2] > 0) {  // 只要左边有座位,就往左边移动
                res = getMin(left, mid, node * 2);
            } else {
                res = getMin(mid + 1, right, node * 2 + 1);
            }
            return res;
        }

        public void update(int index, int value) {
            update(index, value, left, right, root);
        }

        public void update(int index, int value, int left, int right, int node) {
            if (left == right) {
                hasSeatArr[node] = value;
                return;
            }
            // 这里需要对arr进行更新操作
            int mid = (left + right) / 2;
            if (index <= mid) {
                update(index, value, left, mid, node * 2);
            }
            if (index > mid) {
                update(index, value, mid + 1, right, node * 2 + 1);
            }
            hasSeatArr[node] = Math.max(hasSeatArr[node * 2], hasSeatArr[node * 2 + 1]); // 只要有一个有位置就可以了
        }
    }


作者写题解的时候说是接近双百,但是我抄他的跑了一下,和赋值他的跑了一下,排名都不高。可能当年写题解写的比较早

题解2


TreeSet是红黑树
PriorityQueue是完全二叉树
前者的 iterator是有序的,后者是不保证有序的

这里就是简单的将treeSet改成了PriorityQueue

    class SeatManager {
        // 将初始化的时间给优化了,min用1开始发放,不断累加。如果有回收的作为用treeSet收集。如果treeSet不为空,优先从treeSet弹出安排座位
//        TreeSet<Integer> treeSet = new TreeSet<>();
        private final PriorityQueue<Integer> queue = new PriorityQueue<>();

        int min = 1;

        public SeatManager(int n) {
        }

        public int reserve() {
            if (queue.isEmpty()) {
                int res = min;
                min++;
                return res;
            } else {
                return queue.poll();
            }
        }

        public void unreserve(int seatNumber) {
            queue.add(seatNumber);
        }
    }

在这里插入图片描述

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部