力扣（leetcode）每日一题 1845 座位预约管理系统| treeSet和priority Queue的区别|线段树
之前发过一篇，感觉还有深挖的地方，于是又补充一些信息
这题目虽然是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);}}
